在图论中,最短路径问题是寻找从一个结点(源结点)到另一个结点(目标结点)的路径,使得该路径的总权重最小。对于有向无环图(DAG)和权重相等的有向图,广度优先搜索(BFS)是一种高效的最短路径算法。然而,对于一般的有向图,尤其是含有环和不同权重的边时,BFS不一定能找到最短路径。本文将通过一个具体的例子展示一种情况,即对于给定的有向图G=(V,E),以及特定的源结点s∈V和一组树边E_s,使得在每个子图(V,E_s)中,从源结点s到每个结点v∈V的唯一简单路径是G中的一条最短路径,但无论邻接链表中结点之间的次序如何,这组树边E_s都不能通过在图G上运行BFS来获得。
考虑一个有向图G,其顶点集V={A, B, C, D, E}和边集E={(A,B,1), (A,C,1), (B,D,1), (C,D,2), (D,E,1), (C,E,3)}。其中每条边的格式为(u,v,w),表示从顶点u到顶点v有一条权重为w的边。