最短路径（dijkstra算法）

最短路径（dijkstra算法）

带权有向图，求源到其他所有各顶点的最短路径长度。 单源最短路径问题，但不能处理带负权边的图  最短路：dijkstra算法

算法的实现模板：

#define MaxN 10010 //MaxN是点的个数#define MaxInt 200000000 //MabInt表示不可达int map[MaxN][MaxN],dist[MaxN];bool mark[MaxN];int start,end;int dijlstra(){ for(int i=1;i<=end;i++) dist[i]=MaxInt; memset(mark,0,sizeof(mark)); dist[start]=0; //把起点并入集合，搜索的就可以从起点寻找第一条最短的边了 for(int i=1;i<=end-1;i++) { min1=MaxInt; for(int j=1;j<=end;j++) //查找到原集合的最短的边 { if(!mark[j] && dist[j]0) { temp=dist[minj]+map[minj][j]; if(temp

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。