【软考】图的最短路径应用

www.net130.com     日期:2005-9-19    浏览次数:
出处:JTLs Blog
功能是按给出的一张含有路径长度地图,从地图中所有路径中找出任意两个城市间的最短路径,算出最短路径的长度及其途经的城市。

使用邻接矩阵作为图的结构,使用队列记录最短路径上途经的城市,使用迪杰斯特拉(Dijkstra)算法,详细说明请见代码中注释。

分为有向图和无向图两部分
有向图是指每条路径都是有方向的,只能按图中固定的方向走。
无向图是指每条路径都是双向的,就像正常的公路。
R>源程序及可执行程序
save File: Click to Download

地图如下:
Click to Open in New Window


程序结果,以郑州为起点,列出其到各个城市的最短路径。
Click to Open in New Window


列出各个城市间的距离表,分别为有向图和无向图的邻接矩阵。
Click to Open in New Window
Click to Open in New Window

本新闻共2页,当前在第1页  1  2  

相关新闻
推荐文章