迪杰斯特拉(dijkstra)算法.ppt

迪杰斯特拉dijkstra算法 用邻接矩阵GA来表示带权有向图s为已找到从v出发的最短路径的终点的集合它的初始状态为空集那么从v出发到图上其余各顶点可能达到的最短路径长度的初值为dist[i]=cost[v0,vi](viV) 选择vj使得dist[j]=min{dist[i]|(viV-s)} vj就是当前求得的一条从v0出发的最短路径的终点令s=s{j} 修改从v出发到集合v-s上任一顶点vk