单源最短路径算法--Dijkstra算法和Bellman-Ford算法
<div id="cnblogs_post_body">Dijkstra算法算法流程：
(a) 初始化：用起点v到该顶点w的直接边(弧)初始化最短路径，否则设为&infin;；
(b) 从未求得最短路径的终点中选择路径长度最小的终点u：即求得v到u的最短路径；
(c) 修改最短路径：计算u的邻接点的最短路径，若(v,&hellip;,u)+(u,w)<(v,&hellip;,w)，则以(v,&hellip;,u,w)代替。
(d) 重复(b)-(c)，直到求得v到其余所有顶点的最短路径。
特点：总是按照从小到大的顺序求得最短路径。
假设一共有N个节点，出发结点为s，需要一个一维数组prev来记录前一个节点序号，一个一维数组dist来记录从原点到当前节点最短路径（初始值为s到Vi的边的权值，没有则为+&infin;），一个二维数组weights来记录各点之间边的权重，按以上流程更新prev和dist。
参考代码：
<div class="cnblogs_code">#include <iostream> #include <cstdlib> using namespace std; void Dijkstra(int n,int s,int *dist,int *prev,int w[][4]){ int maxint = 65535; bool *visit = new bool; for (int i = 0; i < n; i++) { dist = w; visit = false; if (dist != maxint) { prev = s; } } dist = 0; visit = true; for (int i = 0; i < n; i++) { int temp = maxint; int u = s; for (int j = 0; j < n; j++) { if ((!visit) && (dist < temp)) { u = j; temp = dist; } } visit = true; for (int j = 0; j < n; j++) { if (!visit) { int newdist = dist + w; if (newdist < dist) { dist = newdist; prev = u; } } } } delete []visit;} int main(){ int n,v,u; int weight[4][4]={ 0,2,65535,4, 2,0,3,65535, 65535,3,0,2, 4,65535,2,0 }; int q = 0; int way[4]; int dist[4]; int prev[4]; int s = 1; int d = 3; Dijkstra(4, s, dist, prev, weight); cout<<"The least distance from "<<s<<" to "<<d<<" is "<<dist<<endl; int w = d; while (w != s) { way++] = prev; w = prev; } cout<<"The path is "; for (int j = q-1; j >= 0; j--) { cout<<way<<" ->"; } cout<<d<<endl; return 0;}
页:
[1]