图论及其应用(2)

dist[j] = dist[u] + cost[u][j];

path[j] = u;//path记录了通过路径的顶点 }

}

for(i = 0;i < n;i++)//打印结果 if(s[i] == 1) {

u = i;

while(u != v0) {

cout<

cout<

} else

cout<

return 0; }

四．实验结果

该程序在vc6.0下调试通过，按程序提示的要求输入相应的数据。如提示请输入顶点数和边数时，按前面给的重庆交通网络图需输入9 13；接着提示输入第一个顶点的信息，按要求可输入Nanan，随后依次输入剩余八个点的信息；紧接着提示输入第一条边的起始顶点编号和终止顶点编号，输入1 2，后又提示此边权值，输入10，其余各边同样按这个步骤输入。

这些必要信息输入完后，要求输入起始点的编号，由于篇幅有限，这里以1为例，显示其结果为：

如果在该类网中动态的增加顶点和边，只需在运行程序时，输入增加以后的总顶点数、边数、顶点信息和边的起始顶点编号和终止顶点编号即可。

五．总结

Dijkstra算法是求最短路的一个经典算法，其时间复杂度为O（n）。最短路径对交通、道路问题的研究有重要的意义。该算法能够解决实际生活中的道路选择问题，在导航系统中也有很广泛的应用。

参考文献：

[1]鲍培明．距离寻优中的Dijkstra 算法【J】．计算机研究与发展，2001，23(9)：550—562．

[2] 徐风生，李天志．所有最短路径的求解算法【J】．计算机工程与应用，2006．28(12)：83—84．

[3]张林广．基于配对堆改进的Dijkstra算法【J】．中国图像图形学报，2007，5(12)：922—924．

[4]冯桂莲.基于Dijkstra算法的最短路径的实现【J】.青海大学学报，2007，25（1）：98-102.

2

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库图论及其应用(2)在线全文阅读。