最短路算法（Floyd，Dijkstra，.Bellman |
您所在的位置：网站首页 › 最短路算法的基本思想是谁提出的 › 最短路算法（Floyd，Dijkstra，.Bellman |
最短路算法（Floyd，Dijkstra，.Bellman
|
最近复习了下最短路，顺便写篇博客加强下自己的印象
*核心思想： 要缩短两点之间的距离，就需要第三个顶点来松弛。 *具体步骤： 依次用1到n号顶点做中转，松弛任意两点之间的距离。 因为这个算法比较简单，就直接上代码了； #include using namespace std; const int N=2000; int main() { int maps[N][N]; for(int i=1;icin>>a>>b>>c; maps[a][b]=c; maps[b][a]=c;//假设是双向路 } for(int i=1;i int v,w; }E; vector edge[maxn]; int dis[maxn]; int main(){ int n,m; int u; while(scanf("%d%d",&n,&m),n){ //初始化 for(int i=1;i scanf("%d%d%d",&u,&E.v,&E.w); edge[u].push_back(E); } priority_queue que; while(!que.empty()) que.pop(); dis[1]=0; que.push(P(dis[1],1)); while(!que.empty()){ P now=que.top(); que.pop(); int nowu=now.second; for(int i=0;i dis[E.v]=dis[nowu]+E.w; que.push(P(dis[E.v],E.v)); } } } for(int i=1;i //存图 for(int i=1;i if(dis[v[i]]>dis[u[i]]+w[i]){ dis[v[i]]=dis[u[i]]+w[i]; check=1; } } if(check==0) break; } for(int i=1;i |
1.Floyd算法 我认为是最短路最简单的算法，但一般来说简单的都不是什么好东西，因为复杂度比较高；【本文地址】
今日新闻 |
推荐新闻 |