如果v_i与v_j之间存在一条无方向的边相关联，说明v_i与v_j两点之间可以互达。当v_i与v_j之间至少有两条边相关联时，留下一条最短边，去掉其他关联边。对于无向图最短路的求解，Dijkstra算法同样有效。

无向图的标号方法与有向图相同，路线的起点标号，将标号的第一步改为：找出所有一端v_i已标号、另一端v_j未标号的边，集合为B={[i，j]v_i已标号，v_j未标号}，如果这样的边不存在或v_t已标号，则计算结束。点标号和边标号的计算公式相同。

【例7.4】 要在8个城市间建立如图7-9所示的公路交通网。已知城市与城市间的路可以互达，网络边上的数据表示城市间公路的距离，用Dijkstra算法求解城市1到其他城市间

图7-8

公路的最小距离。

解 起点v₁标号。

第一轮，一端已标号另一端未标号的边集合B={[1，2]，[1，3]，[1，4]}，k（1，2）=b（1）+c₁₂=0+4=4，k（1，3）=0+5=5，k（1，4）=0+2=2，将边的标号用圆括号填在边上。min{k（1，2），k（1，3），k（1，4）}=min{4，5，2}=2(www.daowen.com)

k（1，4）=2最小，点v₄标号2，见图7-10a。

图7-9

第二轮，图7-10a中，B={[1，2]，[1，3]，[4，3]，[4，7]}，k（4，3）=2+1=3，k（4，7）=2+8=10，min{k（1，2），k（1，3），k（4，3），k（4，7）}=min{4，5，3，10}=3，k（4，3）=3最小，点v₃标号3，见图7-10b。

继续标号，第三轮得到点v₂的标号，见图7-10c。第四轮得到两个点v₅与v₇的标号，见图7-10d。第五轮得到点v₆的标号，见图7-10e。第六轮得到点v₈的标号，见图7-10f。所有点得到标号，计算结束。

根据图7-10f所示，v₁到v₂，v₃，…，v₈的最短路分别是：p₁₂={v₁，v₂}，p₁₃={v₁，v₄，v₃}，p₁₄={v₁，v₄}，p₁₅={v₁，v₄，v₃，v₅}，p₁₆={v₁，v₄，v₃，v₅，v₆}，p₁₇={v₁，v₄，v₃，v₇}，p₁₈={v₁，v₄，v₃，v₅，v₈}。最短路长分别是：L₁₂=4，L₁₃=3，L₁₄=2，L₁₅=6，L₁₆=8，L₁₇=6，L₁₈=18。