14讲——最短路问题

Dijkstra算法图的存储邻接矩阵算法基本思想按照最短路径的长度递增的次序依次求得原点到其余各点的最短路径具体步骤0设置辅助数组Dist,其中每个分量Dist[k]表示当前所求得的从源点到期于各个顶点k的最短路径1在所有从原点出发的边中去一条权值最小的边即为第一条最短路2修改其他各顶点的Dist[k]的值3选出下一条最短路径重复以上操作直到找到所有最短路例一#includebits/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(i0;in;i){ visit[i]1; Dist[i]inf; for(j0;jn;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) { Mininf;//最短最短边 for(i0;in;i) { if(Map[now][i]!inf) Dist[i]min(Dist[i],Map[now][i]);//如果相通更新最短路 if(visit[i]Dist[i]Min) { nexti;MinDist[i]; }//选择最短最短路 } if(Mininf) break;//死路 nownext; visit[now]0; } if(Dist[targe]inf) puts(-1); else printf(%d\n,Dist[targe]); } return 0; }例二神奇的思路设置一个虚拟起点和虚拟终点