文章責(zé)編:ak47
看了本文的網(wǎng)友還看了 功能是按給出的一張含有路徑長度地圖,從地圖中所有路徑中找出任意兩個(gè)城市間的最短路徑,算出最短路徑的長度及其途經(jīng)的城市。
使用鄰接矩陣作為圖的結(jié)構(gòu),使用隊(duì)列記錄最短路徑上途經(jīng)的城市,使用迪杰斯特拉(Dijkstra)算法,詳細(xì)說明請(qǐng)見代碼中注釋。
分為有向圖和無向圖兩部分
有向圖是指每條路徑都是有方向的,只能按圖中固定的方向走。
無向圖是指每條路徑都是雙向的,就像正常的公路。
R>源程序及可執(zhí)行程序
File: Click to Download
地圖如下:
程序結(jié)果,以鄭州為起點(diǎn),列出其到各個(gè)城市的最短路徑。
列出各個(gè)城市間的距離表,分別為有向圖和無向圖的鄰接矩陣。
代碼部分:
隊(duì)列結(jié)構(gòu):