用dijkstra算法计算源点到个结点的最短路径.谢谢亲爱的朋友~

Question

用dijkstra算法计算源点到个结点的最短路径.谢谢亲爱的朋友~

Answer 1

(这里描述的是从节点1开始到各点的dijkstra算法,其中Wa->b表示a->b的边的权值,d(i)即为最短路径值)
1． 置集合S={2,3,...n}, 数组d(1)=0, d(i)=W1->i(1,i之间存在边) or +无穷大(1.i之间不存在边) 2． 在S中,令d(j)=min{d(i),i属于S},令S=S-{j},若S为空集则算法结束,否则转3
3． 对全部i属于S,如果存在边j->i,那么置d(i)=min{d(i), d(j)+Wj->i},转2