贪心算法求最短路径问题讲解

《贪心算法求最短路径问题讲解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#include#includeconstintsize=5;//返回最短路径的长度//edge[size][size]，输入参数图信息//nstart,ndest，起点和终点//path[size]返回路径intdijkstra(intedge[size][size],intnstart,intndest,intpath[size]){intmindis[size];//起点到终点的最短路径产度boolins2[size];//标志各点是否在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<<"路径长度为："<