IndexHelp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 s = PickSource() t = PickSink() dist_s[s] = 0 PQ_s.Insert(s,dist_s[s]) dist_t[t] = 0 PQ_t.Insert(t,dist_t[t]) met = FALSE while not met: v = PQ_s.DeleteMin() permanent_s[v] = TRUE if permanent_t[v]: met = TRUE for w in Neighborhood(v): if dist_s[w] == gInfinity: pred_s[w] = v dist_s[w] = dist_s[v] + length[(v,w)] PQ_s.Insert(w,dist_s[w]) elif dist_s[w] > dist_s[v] + length[(v,w)]: pred_s[w] = v dist_s[w] = dist_s[v] + length[(v,w)] PQ_s.DecreaseKey(w,dist_s[w]) if permanent_t[w]: if currentlength > dist_s[w] + dist_t[w]: currentlength = dist_s[w] + dist_t[w] SetBridge(v,w) v = PQ_t.DeleteMin() permanent_t[v] = TRUE if permanent_s[v]: met = TRUE for w in Neighborhood(v): if dist_t[w] == gInfinity: pred_t[w] = v dist_t[w] = dist_t[v] + length[(v,w)] PQ_t.Insert(w,dist_t[w]) elif dist_t[w] > dist_t[v] + length[(v,w)]: pred_t[w] = v dist_t[w] = dist_t[v] + length[(v,w)] PQ_t.DecreaseKey(w,dist_t[w]) if permanent_s[w]: if currentlength > dist_s[w] + dist_t[w]: currentlength = dist_s[w] + dist_t[w] SetBridge(v,w) ShowPath(Bridge)