貪心算法求最短路徑問題講解

《貪心算法求最短路徑問題講解》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、#include#includeconstintsize=5;//返回最短路徑的長度//edge[size][size]，輸入?yún)?shù)圖信息//nstart,ndest，起點和終點//path[size]返回路徑intdijkstra(intedge[size][size],intnstart,intndest,intpath[size]){intmindis[size];//起點到終點的最短路徑產(chǎn)度boolins2[size];//標(biāo)志各點是否在s2中//初始化inti;for(

2、i=0;i

3、的最小值的點intnminlen=INT_MAX;//最短路徑長度的最小值intnpoint=-1;//擁有最小值的點for(i=0;i

4、t][i]

5、;elseif(path[ndest]==ndest)cout<<'v'<v"<

6、edge[1][3]=10;edge[2][4]=7;edge[3][0]=15;edge[3][1]=12;edge[3][4]=7;intpath[size];//記錄最短路徑信息intnpathlength=dijkstra(edge,0,4,path);//計算從v0到v4的最短路徑長度if(npathlength==INT_MAX)cout<<"沒有v0到v4路徑可通"<

7、cout<<"路徑長度為："<