Dijkstra算法步骤

最短路问题Dijkstra算法步骤（wij≥0）在运算过程中，我们每一步都给一个新的点vj进行标号，标号分为两部分，其中标号中的第二个数值表示从起点vs到该点的最短距离P(vj)，第一个数值表示从起点到该点的最短路线上的前一个点。用λ(vj)表示从vs到vj的最短路线上vj的前一个点的下标。用Si表示进行到第i步时，已经被标号的点的集合。（1）给起点vs标号(0,0)，并令S0={vs}。标号中的第二个数值P(vs)=0，表示从起点到该点的最短距离为0；由于是起点，因此标号中的第一个数值设为0。寻找从vs发出的所有弧，求出这些弧的权与P(vs)之和的最小值，即min{()}ssjjPv(j为从起点vs发出的所有弧的终点的下标)对以上最小值所对应的点进行标号，并确定S1。（2）继续探寻从已标号的点出发、终点为未标号点的弧，求出已标号点的P值与相应弧的权之和，对其中最小值所对应的点进行标号，并确定S2。（3）以此步骤进行，直到找不到从已标号点出发、终点为未标号点的弧时，就得到了从起点vs到各个点的最短距离。如果最后标号进行不下去时还存在未标号的点，则意味着从起点vs不存在到达该点的路线。（4）利用逆向思维，可以找到从起点到任何一点的最短路线。