定义概览
Dijkstra算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。
问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。（单源最短路径）。
原理及详解
基于邻接矩阵的C++代码
普通Dijkstra代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
int n, e[maxv][maxv] = {{0,4,inf,2,inf}, {4,0,4,1,inf}, {inf,4,0,1,3}, {2,1,1,0,7}, {inf,inf,3,7,0}}; //邻接矩阵 int dis[maxv], pre[maxv]; //pre用来标注当前节点的前一个节点 bool visit[maxv] = {false}; void Dijkstra(int s){ fill(dis, dis+maxv, inf); //给所有的距离初始化为inf dis[s] = 0; //对于节点自身为0 for(int i=0;i<maxv;i++)pre[i] = i; //初始状态设每个点的前驱为自身 for(int i=0;i<maxv;i++){ //算法核心 int u = -1, minn = inf;//u代表节点，minn为最小值 for(int j=0;j<maxv;j++){ //此循环用来找到当前节点最近未访问的点 if(visit[j]==false && dis[j] < minn){ u = j; minn = dis[j]; } } if(u == -1)return; //没有对应的路径 visit[u] = true; //当前节点找到，对应于算法中加入到已访问集合 for(int v=0;v<maxv;v++){ //更新路径，如果u到其他未被选取点的距离+起点到u的距离小于起点到其他未被选取点的距离，则更新当前点的前驱为u if(visit[v] == false && e[u][v]!=inf && dis[u]+e[u][v] < dis[v]){ dis[v] = dis[u]+e[u][v]; pre[v] = u; } } } } |
在求最短路径的同时，求出最短路径的个数，并求得最短路径上的总价值（使用大于号）或者花费（使用小于号）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
int w[maxv], weight[maxv], num[maxv]; //起点到当前点的总价值，weight是静态当个点的价值，num是最短路径的个数 void Dijkstra2(int s){ //路径最短，点权权值最大，并且输出个数和路径 fill(dis, dis+maxv, inf); //给所有的距离初始化为inf fill(w, w+maxv, 0); fill(num, num+maxv, 0); dis[s] = 0; //对于节点自身为0 num[s] = 1; w[s] = weight[s]; for(int i=0;i<maxv;i++)pre[i] = i; //初始状态设每个点的前驱为自身 for(int i=0;i<maxv;i++){ //算法核心 int u = -1, minn = inf;//u代表节点，minn为最小值 for(int j=0;j<maxv;j++){ //此循环用来找到当前节点最近未访问的点 if(visit[j]==false && dis[j] < minn){ u = j; minn = dis[j]; } } if(u == -1)return; //没有对应的路径 visit[u] = true; //当前节点找到，对应于算法中加入到已访问集合 for(int v=0;v<maxv;v++){ //更新路径，如果u到其他未被选取点的距离+起点到u的距离小于起点到其他未被选取点的距离，则更新当前点的前驱为u if(visit[v] == false && e[u][v] != inf){ if(dis[u] + e[u][v] < dis[v]){ dis[v] = dis[u] + e[u][v]; //更新最短路径 num[v] = num[u]; //显然v最短路径要经过u，而u到v是固定的，因此num[v] = num[u] w[v] = w[u] + weight[v]; //更新路径的价值，路径上经过所有价值点的总和 pre[v] = u; }else if(dis[u] + e[u][v] == dis[v]){ //当有多个最短路径时 num[v] = num[u] + num[v]; //两个相加 if(w[u] + weight[v] > w[v]){ //如果价值更大则覆盖掉原先的 w[v] = w[u] + weight[v]; pre[v] = u; } } } } } } |
完整代码
注意代码中有两个Dijkstra代码，第一个是普通的Dijkstra代码，第二个是求有多少个最短路径，最短路径上增加价值或花费。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
#include<iostream> #include<cstdio> #define maxv 5 #define inf 0x7fffffff using namespace std; //邻接表 int n, e[maxv][maxv] = {{0,4,inf,2,inf}, {4,0,4,1,inf}, {inf,4,0,1,3}, {2,1,1,0,7}, {inf,inf,3,7,0}}; //邻接矩阵 int dis[maxv], pre[maxv]; //pre用来标注当前节点的前一个节点 bool visit[maxv] = {false}; void Dijkstra(int s){ fill(dis, dis+maxv, inf); //给所有的距离初始化为inf dis[s] = 0; //对于节点自身为0 for(int i=0;i<maxv;i++)pre[i] = i; //初始状态设每个点的前驱为自身 for(int i=0;i<maxv;i++){ //算法核心 int u = -1, minn = inf;//u代表节点，minn为最小值 for(int j=0;j<maxv;j++){ //此循环用来找到当前节点最近未访问的点 if(visit[j]==false && dis[j] < minn){ u = j; minn = dis[j]; } } if(u == -1)return; //没有对应的路径 visit[u] = true; //当前节点找到，对应于算法中加入到已访问集合 for(int v=0;v<maxv;v++){ //更新路径，如果u到其他未被选取点的距离+起点到u的距离小于起点到其他未被选取点的距离，则更新当前点的前驱为u if(visit[v] == false && e[u][v]!=inf && dis[u]+e[u][v] < dis[v]){ dis[v] = dis[u]+e[u][v]; pre[v] = u; } } } } int w[maxv], weight[maxv], num[maxv]; //起点到当前点的总价值，weight是静态当个点的价值，num是最短路径的个数 void Dijkstra2(int s){ //路径最短，点权权值最大，并且输出个数和路径 fill(dis, dis+maxv, inf); //给所有的距离初始化为inf fill(w, w+maxv, 0); fill(num, num+maxv, 0); dis[s] = 0; //对于节点自身为0 num[s] = 1; w[s] = weight[s]; for(int i=0;i<maxv;i++)pre[i] = i; //初始状态设每个点的前驱为自身 for(int i=0;i<maxv;i++){ //算法核心 int u = -1, minn = inf;//u代表节点，minn为最小值 for(int j=0;j<maxv;j++){ //此循环用来找到当前节点最近未访问的点 if(visit[j]==false && dis[j] < minn){ u = j; minn = dis[j]; } } if(u == -1)return; //没有对应的路径 visit[u] = true; //当前节点找到，对应于算法中加入到已访问集合 for(int v=0;v<maxv;v++){ //更新路径，如果u到其他未被选取点的距离+起点到u的距离小于起点到其他未被选取点的距离，则更新当前点的前驱为u if(visit[v] == false && e[u][v] != inf){ if(dis[u] + e[u][v] < dis[v]){ dis[v] = dis[u] + e[u][v]; //更新最短路径 num[v] = num[u]; //显然v最短路径要经过u，而u到v是固定的，因此num[v] = num[u] w[v] = w[u] + weight[v]; //更新路径的价值，路径上经过所有价值点的总和 pre[v] = u; }else if(dis[u] + e[u][v] == dis[v]){ //当有多个最短路径时 num[v] = num[u] + num[v]; //两个相加 if(w[u] + weight[v] > w[v]){ //如果价值更大则覆盖掉原先的 w[v] = w[u] + weight[v]; pre[v] = u; } } } } } } void printPath(int v){ if(v == 0){ printf("%d", v); return; } printPath(pre[v]); printf("%d ", v); } int main(){ Dijkstra(0); cout<<"distance"<<endl; for(int i=0;i<maxv;i++){ cout<<dis[i]<<endl; } cout<<endl<<"pre"<<endl; for(int i=0;i<maxv;i++){ cout<<pre[i]<<endl; } return 0; } |
Acknowledgement
感谢柳婼提供的思路
