最短路问题

【文件属性】：

文件名称：最短路问题

文件大小：198KB

文件格式：DOC

更新时间：2021-02-02 02:22:49

算法资源

．Dijkstra算法 Dijkstra算法是解决从网络中任一顶点（源点）出发，求它到其他各顶点（终点）的最短路径问题（或称单源点最短路径问题）。其实Dijkstra算法就是标号法。 Dijkstra算法如下： (1) 假设用带权的邻接矩阵a来表示带权有向图，a[i,j]表示弧上的权值。若不存在，则置a[I,j]为无穷大。S为已找到从V出发的最短路径的终点的集合，它的初始状态为空集。那么，从v0出发到图上其余各顶点(终点)Vi可能达到的最短路径长度的初值为：dist[I]:=a[v0,I]。 (2) 选择Vj，使得d[j]:=min{dist[I],Vi∈V-S}, Vj就是当前求得的一条从V出发的最短路径的终点。令S=S∪{J}。 (3) 修改从Vj 出发到集合V-S上任一顶点Vk可达的最短路径长度。如果d[j]+a[j,k]