🏷️ 知识点：带权图最短路径

已知带权连通无向图 G=(V,E)，其中 V={v₁,v₂,v₃,v₄,v₅,v₆,v₇}， E={(v₁,v₂,10),(v₁,v₃,2),(v₃,v₄,2),(v₃,v₆,11),(v₂,v₅,1),(v₄,v₅,4),(v₄,v₆,6),(v₅,v₇,7),(v₆,v₇,3)}。 括号外的数表示边权。从源点 v₁ 到顶点 v₇ 的最短路径上经过的顶点序列是（　　）。

A. v₁,v₂,v₅,v₇ B. v₁,v₃,v₄,v₆,v₇ C. v₁,v₃,v₄,v₅,v₇ D. v₁,v₂,v₅,v₄,v₆,v₇

[tag_link]

正确答案：B

结论

选 B，路径长度为 2+2+6+3=13。

推导

候选路径长度分别为 A=10+1+7=18、B=13、C=2+2+4+7=15、D=10+1+4+6+3=24。因此最短路径为 v₁→v₃→v₄→v₆→v₇。

易错点

必须把边权累加并比较总长度，不能按边数或局部最小边选择。