最短路---dijsktra--邻接矩阵
1 const int MAXINT = 32767; 2 const int MAXNUM = 10; //点的个数 3 int dist[MAXNUM]; 4 int prev[MAXNUM]; 5 6 int A[MAXUNM][MAXNUM]; 7 8 void Dijkstra(int v0) 9 { 10 bool S[MAXNUM]; // 新建一个标记数组,判断是否已存入该点到S集合中; 11 int n=MAXNUM; 12 for(int i=1; i<=n; ++i) 13 { 14 dist[i] = A[v0][i]; //将该点的邻接矩阵复制到dist[]一维数组中; 15 S[i] = false; // 初始都未用过该点; 16 if(dist[i] == MAXINT) 17 prev[i] = -1; 18 else 19 prev[i] = v0; //记录该点的上一节点是现在处理的源点,如果不联通为-1; 20 } 21 dist[v0] = 0; //dist表示原点v0到该点的最短距离; 22 S[v0] = true; //将源点标记为已经访问; 23 for(int i=2; i<=n; i++) //循环n-1次,保证找到每一个点; 24 { 25 int mindist = MAXINT; //标记当前的最小距离,初始化为最大; 26 int u = v0; // 找出当前未使用的点j的dist[j]最小值 27 for(int j=1; j<=n; ++j) 28 if((!S[j]) && dist[j]<mindist) 29 { 30 u = j; // u保存当前邻接点中距离最小的点的号码 31 mindist = dist[j]; 32 } //找出了距离该源点最近的那个点,u记录了点的编号; 33 S[u] = true; 34 for(int j=1; j<=n; j++) 35 if((!S[j]) && A[u][j]<MAXINT) //找没有被使用过的点,且与u是联通的点; 36 { 37 if(dist[u] + A[u][j] < dist[j]) //在通过新加入的u点路径找到离v0点更短的路径 ;(如果该点距离原点的距离比从u点过度过来的距离长,则当前的最短路就改变) 38 { 39 dist[j] = dist[u] + A[u][j]; //更新dist 40 prev[j] = u; //记录前驱顶点 41 } 42 } 43 } 44 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。