14讲——最短路问题

Dijkstra算法

图的存储（邻接矩阵）

算法基本思想：

按照最短路径的长度递增的次序，依次求得原点到其余各点的最短路径

具体步骤：

（0）设置辅助数组Dist,其中每个分量Dist[k]表示：当前所求得的从源点到期于各个顶点k的最短路径

（1）在所有从原点出发的边中去一条权值最小的边，即为第一条最短路

（2）修改其他各顶点的Dist[k]的值

（3）选出下一条最短路径，重复以上操作，直到找到所有最短路

例一：

#include<bits/stdc++.h> using namespace std; #define inf 0x7FFFFFFF #define M 201 int Map[M][M],Dist[M],visit[M]; int main(){ int n,m,i,j,a,b,dis,now,Min,next,targe; while(scanf("%d%d",&n,&m)==2){ for(i=0;i<n;i++){ visit[i]=1; Dist[i]=inf; for(j=0;j<n;j++){ Map[i][j]=inf; } }//初始化数据 while(m--){ scanf("%d%d%d",&a,&b,&dis); Map[a][b]=min(Map[a][b],dis);//防重边 Map[b][a]=Map[a][b];//无向图 } scanf("%d%d",&now,&targe); Dist[now]=0; visit[now]=0; while(now!=targe) { Min=inf;//最短最短边 for(i=0;i<n;i++) { if(Map[now][i]!=inf) Dist[i]=min(Dist[i],Map[now][i]);//如果相通，更新最短路 if(visit[i]&&Dist[i]<Min) { next=i;Min=Dist[i]; }//选择最短最短路 } if(Min==inf) break;//死路 now=next; visit[now]=0; } if(Dist[targe]==inf) puts("-1"); else printf("%d\n",Dist[targe]); } return 0; }

例二：

神奇的思路：设置一个虚拟起点和虚拟终点