最短路径原理

这样答：

1、标记起点0，设p（0）=空；d（0）=0

2、从距离矩阵L中读取0到各点距离值：d（1）=∞,d（2）=10，d（3）=∞，d（4）=30，d （5）=100；p（1）=空，p（2）=0，p（3）=空；p（4）=0，p（5）=0

3、取最小距离D，mind=10，标记点2，记d（2）=10；p（2）=0

4、重新计算0点到其它未标记点的最短距离：

d（1）=min｛d（1），d（2）+L（2，1）｝=｛∞，10+∞｝=∞p（1）=空

d（3）=min｛d（3），d（2）+L（2，3）｝=｛∞，10+50｝=60p（3）=2

d（4）=min｛d（4），d（2）+L（2，4）｝=｛30，10+∞｝=30p（4）=0

d（5）=min｛d（5），d（2）+L（2，5）｝=｛100，10+∞｝=100p（5）=0

5、取最小距离D，mind=30，标记点4，记d（4）=30；p（4）=0

6、重新计算0点到其它未标记点的最短距离：

d（1）=min｛d（1），d（4）+L（4，1）｝=｛∞，30+∞｝=∞p（1）=空

d（3）=min｛d（3），d（4）+L（4，3）｝=｛60，30+20｝=50p（3）=4

d（5）=min｛d（5），d（4）+L（4，5）｝=｛100，30+60｝=90p（5）=4

7、取最小距离D，mind=50，标记点3，记d（3）=50；p（3）=4

8、重新计算0点到其它未标记点的最短距离：

d（1）=min｛d（1），d（3）+L（3，1）｝=｛∞，50+∞｝=∞p（1）=空

d（5）=min｛d（5），d（3）+L（3，5）｝=｛100，50+10｝=60p（5）=3

9、取最小距离D，mind=60，标记点5，记d（5）=60；p（5）=3

此时标记点为终点，算法结束，根据p数组所记录的点倒推得最短路线为：

P（5）=3----〉p（3）=4-—〉p（4）=0，即0---4----3----5，最短距离为60。