交通费用问题
设有一城市间的飞机网络，由Pi个城市到Pj所需费用为Cij，令Cij=¥表示第Pi个城市到第Pj个城市不直接通航，Cij的值如下表，设所有城市中只有P1通往外面的航线，因此乘客必须先到P1，然后从P1出发到各地，求P1到P8的最少费用.
2 3 4 5 6 7 8
P8
P1
P2
P3 1 28 2 ¥ 1 ¥ ¥ ¥ 2 ¥ 3 ¥ ¥ 4 ¥ ¥ 5 26 ¥ ¥ 6 8 ¥ 7 7 9 8 ¥ ¥ ¥ 24 ¥ 27 8 7 P6
P5
P7
P4
显然，从P1到P8有若干种走法，每条线路的花费不同，一种简单的想法是，从某一城市Pi出发时，皆选花费最小的城市作为下一站，
这种办法当然可以使当前走下一站的花费最小，但未必使整个线路花费最小。因此考虑这类问题时，每次寻找下一站时不是去考虑局部花费，而应以考虑总体花费最少为原则。
先把顶点集合分成两个集合，集合A包含所有的出发点（包含始发点P1），集合B包括其他点，显然A={ P1}，B={ P2，P3，P4，P5，P6，P7，P8}
为了保证整体线路花费最少的原则，每次开始走时将找出当前从P1出发的所有可能的线路，即从所有可能的出发点分别走（亦即从A中所有点开始往前走），然后在算出各种线路的费用。
具体地，用d(i)表示由P1到Pi的最少费用（d(1)=0），每一次出发时我们都试图找出B中距P1最近的点，即需求出d(j)=min{ d(i)+ Cij}
（i挝A;jB）
d(j)就是当前向下一站出发所选取的最少费用值。，我们最终求出d(8)
具体地 第一步
min{d(1)+c1j}=min{d(1)+c13,d(1)+ c15, d(1)+ c12}=d(1)+ c15=1= d(5) 此时，求得B中点P5，d(5)=1,把P5放入A中。 A= { P1 ,P5}; B={ P2, P3, P4, P6, P7, P8} 第二步
min{d(1)+c1j,d(5)+ c5j}= d(1)+ c13 =2=d(3) 此时，求得B中点P3,把P3放入A中。 A= { P1 ,P5, P3}; B={ P2, P4, P6, P7, P8}
第三步
min{d(1)+c1j,d(5)+ c5j，,d(3)+ c3j }= d(5)+ c52 =9=d(2) 此时，求得B中点P2,把P2放入A中。 此时，求得B中点P2,把P2放入A中。 A= { P1 ,P5, P3 ，P2, }; B={ P4, P6, P7, P8} 第四步
min{d(1)+c1j,d(5)+ c5j，,d(3)+ c3j ，d(2)+ c2j }= d(2)+ c24 =18=d(4) 此时，求得B中点P4,把P4放入A中。 A= { P1 ,P5, P3 ，P2, P4}; B={ P6, P7, P8}
说明：由于P1的下一站可能点P5, P3 ，P2已全部在A中，这样d(1)+c1j已全部隐含在d(2),d(3),d(5)中，故P1一不用再参与计算，可略去（这里用红色标出）。
同理P2也不需再参与计算。 第四步
min{d(5)+ c5j，,d(3)+ c3j ，d(4)+ c4j }= d(4)+ c48 =25=d(8) 此时，求得B中点P8,把P8放入A中。 A= { P1 ,P5, P3 ，P2, P4, P8}; B={ P6, P7 }
计算到此时，P8已在A中。由于P8是线路的终点，因此计算到此结束。
目前A中有6个点，但并非每个点都是花费最少（d(8)=25）. 要想算出最少费用的线路，我们根据上述计算从终点反向去找真正花费为d(8)=25的路线。注意到
d(8) =d(4)+ c48 = d(2)+ c24+ c48= d(5)+ c52 + c24+ c48= d(1)+ c15+ c52 + c24+ c48=25
因此得到花费最小的路线：P1-- P5—P2--- P4--- P8
