player:队列q, marked数组,dist数组,前驱pre数组。这里说数组指的是顶点是按0, V-1编好号的情况,如果没编号,就用一般的symbol table比如map,unordered_map。另外前驱一般情况是多个,即一般应该定义为vector<int> prev[V],而不是int prev[V],如果只求一条最短路径,则可简化为后者。
1 start 入队,q.push(start), marked[start] = true, dist[start] = 0, prev[start] = {start}
2 while 队列不空,出队一个顶点x,做扩展,对于每一个可能扩展出的新结点y(每条边),如过之前没有访问过(marked[y] == false):
1)标记该结点 marked[y] = true
2) dist[y] = dist[x] + 1, pre[y] = x;
3) 如果 y是target:扩展结束,返回dist[y] 或者根据prev 恢复路径
否则:y入队,待扩展。
一般情况marked数组可以用dist或者pre代替,dist或者pre有值就说明该结点被扩展到了。
以上时求一条最短路径的模版,如果是求所有最短路径,同一层扩展出的结点是可以被同一层其他结点再次扩展的,可以用一个levelMarked 数组中转一下,扩展一层的时候,先把扩展出的结点用levelMarked的标记,本层遍历结束后移到marked数组。或者不用marked数组,而用dist,当dist[y]无值(无穷大或者负数)或者有值但dist[x] == dist[y] - 1
路径恢复:
1) 最后的prev就代表了找到点所有路径,一般情况下是一个DAG,用dfs遍历 从T到S的所有路径,注意路径是倒置的,输出时候要reverse.
2) 另一种方法是结点里存储起点到x的所有路径,存储要求高,因为起点到x的路径很多条,每一条路径又是一个结点序列。对于树形图(单前驱,起到到每个点只有唯一路径)可以用一下。但是树形图又不存在最短路径问题,因为只有一条路径。