Dijkstra算法使用于单源最短路且不存在负权边的问题。时间复杂度为O(n^2)。
Dijkstra算法的时间复杂度与图的边无关,所以适合于稠密图
本文以Acwing 849. Dijkstra求最短路I作为例子对Dijkstra算法进行说明
Dijkstra 的整体思路比较清晰
即进行n(n为n的个数)次迭代去确定每个点到起点的最小值 最后输出的终点的即为我们要找的最短路的距离
所以按照这个思路除了存储图外我们还需要存储两个量
图的稠密图的保存使用一个二维数组保存。图的构建和保存的代码如下:
int g[N][N]; //为稠密阵所以用邻接矩阵存储 cin>>n>>m; while(m--) { int x,y,z; cin>>x>>y>>z; g[x][y]=min(g[x][y],z); //如果发生重边的情况则保留最短的一条边 }
为啥是这样等我的算法导论到了再看看吧
int t=-1; //将t设置为-1 因为Dijkstra算法适用于不存在负权边的图 for(int j=1;j<=n;j++) { if(!st[j]&&(t==-1||dist[t]>dist[j]) //该步骤即寻找还未确定最短路的点中路径最短的点 t=j; }
将该点标记为距离已确定
st[j] = true;
这里j从1开始遍历是为了使代码更简洁,而且并不会改变已经确定的距离。
for(int j=1;j<=n;j++) dist[j]=min(dist[j],dist[t]+g[t][j]);
以上就是代码模板的主体部分。
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N=510; int g[N][N]; //为稠密阵所以用邻接矩阵存储 int dist[N]; //用于记录每一个点距离第一个点的距离 bool st[N]; //用于记录该点的最短距离是否已经确定 int n,m; int Dijkstra() { memset(dist, 0x3f,sizeof dist); //初始化距离 0x3f代表无限大 dist[1]=0; //第一个点到自身的距离为0 for(int i=0;i<n;i++) //有n个点所以要进行n次 迭代 { int t=-1; //t存储当前访问的点 for(int j=1;j<=n;j++) //这里的j代表的是从1号点开始 if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j; st[t]=true; for(int j=1;j<=n;j++) //依次更新每个点所到相邻的点路径值 dist[j]=min(dist[j],dist[t]+g[t][j]); } if(dist[n]==0x3f3f3f3f) return -1; //如果第n个点路径为无穷大即不存在最低路径 return dist[n]; } int main() { cin>>n>>m; memset(g,0x3f,sizeof g); //初始化图 因为是求最短路径 //所以每个点初始为无限大 while(m--) { int x,y,z; cin>>x>>y>>z; g[x][y]=min(g[x][y],z); //如果发生重边的情况则保留最短的一条边 } cout<<Dijkstra()<<endl; return 0; }