Dijkstra

1.问题

单源最短路径

2

1.png

最短路径数组就是当前各个节点到A的距离
前驱数组就是相应距离的前一个节点

image.png

此时在V-S中，最短路径数组:

                   matrix
      A     B     C     D     E     F
A    0     6     3     -1     -1    -1
B    6     0     2      5     -1    -1
C    3     2     0      3      4    -1    
D   -1     5     3      0      2     3
E   -1    -1     4      2      0     5
F   -1    -1    -1      3      5     0

distArr={
    B: 6,
    C: 3, //最短
    D: oo,
    E: oo,
    F: oo,
}
prevArr={
    A: nil,
    B: A,
    C: A,
    D: nil,
    E: nil,
    F: nil,
}

将C加入S，此时S={A, C}，V-S={B, C, D, E, F}
然后以C跳板，看是否会改变最短路径数组，
C与V-S中的B、D、E相邻:
distArr[B]=min{distArr[C]+matrix[C, B], distArr[B]}=min{3+2, oo}=5，修改prevArr[B]=C
distArr[D]=min{distArr[C]+matrix[C, D], distArr[D]}=min{3+3, oo}=6，修改prevArr[D]=C
distArr[E]=min{distArr[C]+matrix[C, E], distArr[E]}=min{3+4, oo}=7，修改prevArr[E]=C
此时如下图

image.png