Dijkstra算法――通过边实现松弛 - c++编程基础

算法思想：每次找到离源点最近的顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径.时间复杂度是O(N^2).

基本步骤：

将所有的顶点分为两部分，已知最短路程的顶点集合S和未知最短路径的顶点集合V. 最开始，已知最短路径在集合S中只有源点一个顶点，用book数组来标记哪些点在集合S中.设置源点p到自己的最短路径为0(即dis[p] = 0). 若存在有源点能直接到达的顶点i，则把dis[i] 设为 e[p][i]. 同时把所有其他(源点不能直接到达的)顶点的最短路径设为∞.在集合V的所有顶点中选择一个离源点p最近的顶点u(即dis[u]最小)加入到集合P中. 并考察所有以点u为起点的边，对每一条边进行松弛操作.重复第3步，如果集合V为空，则结束，最终得到的dis数组中的值就是源点到所有顶点的最短路径. 一个点到其余各个顶点的最短路径也叫做“单源最短路径”. 这个Dijkstra同样求最短路径的图同样不能有负权边，因为扩展到负权边的时候会产生更短的路径，有可能破坏了已经更新的点路径不会改变的性质.

Code:

#include 
  
   
#include 
   
     #include 
    
      #define INF 999999 int book[10]; /// 用来纪录已经是最短路径的点 int main(int argc, char const *argv[]) { int i, j, m, n; int q1, q2, q3; int u, v, min; int e[100][100], dis[10]; scanf("%d %d", &n, &m); for(i = 1; i <= n; ++i) { for(j = 1; j <= n; ++j) { if(i == j) { e[i][j] = 0; } else { e[i][j] = INF; } } } for(i = 1; i <= m; ++i) { scanf("%d %d %d", &q1, &q2, &q3); e[q1][q2] = q3; } for(i = 1; i <= n; ++i) { dis[i] = e[1][i]; } book[1] = 1; /// Dijkstra 算法核心 for(i = 1; i < n; ++i) /// 计算n-1次 { min = INF; for(j = 1; j <= n; ++j) { if(dis[j] < min && book[j] == 0) { min = dis[j]; u = j; } } book[u] = 1; for(v = 1; v <= n; ++v) { if(e[u][v] != INF && dis[v] > dis[u] + e[u][v]) { dis[v] = dis[u] + e[u][v]; /// 这个过程就是"松弛" } } } for(i = 1; i <= n; ++i) { printf("%d ", dis[i]); } printf("\n"); system("pause"); return 0; }