dijsktra算法整理

dijsktra算法整理 一、运用 dijsktra算法一般用于求单源最短路径 二、算法思想 已知有向图G(V,E),源顶点s,求s到其他所有顶点的最短长度。 设点集U=∅\varnothing∅,S=V-U;U中存储已经找到从源顶点到该点最小距离dis[u]的点。不断遍历S中的点,找到点p使得dis[p]最小,直到U=V; 三、伪代码 Dijsktra(G,w,s) Input:有向加权图G,边加权函数w,源顶点s Output:s到其所有可达顶点的最短路径 for(v in G) { dis[v]=INF; pre[v]=-1; } d[s]=0; U=U+{s}; Q=V; whil