JAVASCRIPT:HDU&1874&（最短路）Floyd--&&Dijkstra--&&Bellman_Ford--&&SPFA
题目链接：
这题比较基础，拿来练各种刚学会的算法比较好，可以避免好多陷阱，典型的最短路模板题
第一种解法：Floyd算法
算法实现：
使用一个邻接矩阵存储边权值，两两之间能访问的必为一个有限的数，不能访问则为无穷大（用2^29代替）。注意自身和自身距离为0。
对于一对顶点 u 和 v，看看是否存在一个断点 w 使得从 u 经过 w 到 v 比已知的路径更短（包含原始输入中从 u 直接到
v 的路程）。
对所有顶点进行如上松弛操作，得到的结果是两点之间的最短路程，也可判断两点是否连通。
算法缺点：
普通的Floyd算法时间复杂度为O(n^3)，对于数据较多的情况容易TLE。但解决本题 HDU 1874 完全足够。
Floyd算法耗时62MS
#include&stdio.h&
#define Max 0xfffffff
n,m,map[201][201];
min(int a,int b)
& &return a&b?b:a;
& &int i,j,a,b,l;
& &for(i=0;i&n;i++)
&for(j=0;j&n;j++)
&map[i][j]=(i==j?0:Max);
& &for(i=0;i&m;i++)
&scanf("%d%d%d",&a,&b,&l);
&map[a][b]=map[b][a]=min(map[a][b],l);
floyd(int s,int e)
& &int i,j,k;
& &for(k=0;k&n;k++)
&for(i=0;i&n;i++)
&for(j=0;j&n;j++)
& &map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
&printf("%d\n",map[s][e]&Max?map[s][e]:-1);
& &int s,e;
& &while(~scanf("%d%d",&n,&m))
&getmap();
&scanf("%d%d",&s,&e);
&floyd(s,e);
& &return 0;
第二种解法：Dijkstra算法
这个算法比较经典，一般的最短路径都可以用这个来解决，耗时也比较少，不过不能处理负权路径
按路径长度递增次序产生最短路径算法：
　　把V分成两组：
　　（1）S：已求出最短路径的顶点的集合
　　（2）V-S=T：尚未确定最短路径的顶点集合
　　将T中顶点按最短路径递增的次序加入到S中，
　　保证：（1）从源点V0到S中各顶点的最短路径长度都不大于
　　从V0到T中任何顶点的最短路径长度
　　（2）每个顶点对应一个距离值
　　S中顶点：从V0到此顶点的最短路径长度
　　T中顶点：从V0到此顶点的只包括S中顶点作中间
　　顶点的最短路径长度
　　依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的
　　直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和
　　（反证法可证）
　　求最短路径步骤
　　算法步骤如下：
　　1. 初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值
　　若存在&V0,Vi&，d(V0,Vi)为&V0,Vi&弧上的权值
　　若不存在&V0,Vi&，d(V0,Vi)为∝
　　2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S
　　3. 对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的
　　距离值比不加W的路径要短，则修改此距离值
　　重复上述步骤2、3，直到S中包含所有顶点，即S=T为止
Dijkstra算法耗时0MS
#include&stdio.h&
#include&string.h&
#define max 999999
map[201][201];
n,m,st,en,f[201],mark[201];
Dijkstra()
& &int i,j,k,min;
& &memset(mark,0,sizeof(mark));
& &for(i=0;i&n;i++)
&f[i]=map[st][i];
& &f[st]=0;
& &for(i=0;i&n;i++)
&for(j=0;j&n;j++)
&if(!mark[j]&&f[j]&min)
& &min=f[j];
&if(min==max)break;
&mark[k]=1;
&for(j=0;j&n;j++)
&if(!mark[j]&&f[j]&f[k]+map[k][j])
& &f[j]=f[k]+map[k][j];
& &if(f[en]!=max)printf("%d\n",f[en]);
& &else printf("-1\n");
& &int x,y,z,i,j;
& &while(scanf("%d%d",&n,&m)!=EOF)
&for(i=0;i&=n-1;i++)
&for(j=0;j&=n-1;j++)
& &map[i][j]=max;
&for(i=1;i&=m;i++)
& &scanf("%d %d
%d",&x,&y,&z);
& &if(map[x][y]&z)
& &{map[x][y]=map[y][x]=z;}
&scanf("%d
%d",&st,&en);
&Dijkstra();
& &return 0;
第三种解法：Bellman_Ford算法
这个算法也比较好理解，就是不断松弛操作，处理含有负权的路径
对有向图G(V,E)，用贝尔曼-福特算法求以Vs为源点的最短路径的过程：
建立dist[]、Pred[],且dist[s] =
0,其余赋<img STYLE="BorDer-BoTToM-sTYLe: BorDer-riGHT-sTYLe: BorDer-Top-sTYLe: VerTiCAL-ALiGn: BorDer-LeFT-sTYLe: none" ALT="\infty" src="/blog7style/images/common/sg_trans.gif" real_src ="http://upload.wikimedia.org/wikipedia/zh/math/d/2/4/d245777abca64ece2d5d7ca0d19fddb6.png"
TITLE="HDU&1874&（最短路）Floyd--&&Dijkstra--&&Bellman_Ford--&&SPFA" />。Pred[]表示某节点路径上的父节点
对<img STYLE="BorDer-BoTToM-sTYLe: BorDer-riGHT-sTYLe: BorDer-Top-sTYLe: VerTiCAL-ALiGn: BorDer-LeFT-sTYLe: none" ALT="(V_i,V_j) \in E" src="/blog7style/images/common/sg_trans.gif" real_src ="http://upload.wikimedia.org/wikipedia/zh/math/7/a/f/7afbf6e16bde744c0217.png" NAME="image_operate_18291"
TITLE="HDU&1874&（最短路）Floyd--&&Dijkstra--&&Bellman_Ford--&&SPFA" />，比较dist[Vi] + (Vi,Vj)和dist[Vj],并将小的赋给dist[Vj]，如果修改了dist[V_j]则pred[Vj]
=&Vi（松弛操作）
重复以上操作V&& 1次
再重复操作一次，如dist[Vj]
&&dist[Vi]
+ (Vi,Vj),则此图存在负权环。
//v为顶点数
For 每条边(u,v)∈E do
&//对每条边进行遍历
&Relax(u,v,w);
For每条边(u,v)∈E do &
//判断是否存在负权环
dis[u]+w&dis[v]
Then Exit(False)
Bellman_Ford算法耗时15MS，
#include&stdio.h&
#define MAX
m,n,d[208],start,tar;
& &int x,y,w;
}map[2008];
Bellman_Ford()
& &int i,j;
& &for(i=0;i&n;i++)//Init
&d[i]=MAX;
& &d[start]=0;
& &for(i=0;i&n;i++)
&for(j=0;j&2*m;j++)
&if(d[map[j].x]&d[map[j].y]+map[j].w)//relax
x --w--& y
& &d[map[j].x]=d[map[j].y]+map[j].w;
& &if(d[tar]&MAX)
&printf("%d\n",d[tar]);
& &else printf("-1\n");
& &while(scanf("%d%d",&n,&m)!=EOF)
&for(i=0;i&m;i++)
&scanf("%d%d%d",&map[i].x,&map[i].y,&map[i].w);//two
way road ---& & one way
&map[i+m].y=map[i].x;
&map[i+m].x=map[i].y;
&map[i+m].w=map[i].w;
&scanf("%d%d",&start,&tar);
&Bellman_Ford();
& &return 0;
第四种解法：SPFA算法
这种算法可以说是Bellman_Ford算法的优化，就是在Bellman_Ford算法的基础上加上队列实现，
SPFA(Shortest Path Faster
Algorithm)
算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素，并对所有与他相邻的点进行，若某个相邻的点松弛成功，则将其入队。
直到队列为空时算法结束。
这个算法，简单的说就是队列优化的bellman-ford,利用了每个点不会更新次数太多的特点发明的此算法
SPFA——Shortest Path Faster
Algorithm，它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。SPFA的实现甚至比Dijkstra或者Bellman_Ford还要简单：
设Dist代表S到I点的当前最短距离，Fa代表S到I的当前最短路径中I点之前的一个点的编号。开始时Dist全部为+∞，只有Dist[S]=0，Fa全部为0。
维护一个队列，里面存放所有需要进行迭代的点。初始时队列中只有一个点S。用一个布尔数组记录每个点是否处在队列中。
每次迭代，取出队头的点v，依次枚举从v出发的边v-&u，设边的长度为len，判断Dist[v]+len是否小于Dist[u]，若小于则改进Dist[u]，将Fa[u]记为v，并且由于S到u的最短距离变小了，有可能u可以改进其它的点，所以若u不在队列中，就将它放入队尾。这样一直迭代下去直到队列变空，也就是S到所有的最短距离都确定下来，结束算法。若一个点入队次数超过n，则有负权环。
在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k，有办法证明对于通常的情况，k在2左右。
SPFA算法（Shortest Path Faster
Algorithm），也是求解单源最短路径问题的一种算法，用来解决：给定一个加权有向图G和源点s，对于图G中的任意一点v，求从s到v的最短路径。
SPFA算法是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算，他的基本算法和Bellman-Ford一样，并且用如下的方法改进：
1、第二步，不是枚举所有节点，而是通过队列来进行优化
设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。
2、同时除了通过判断队列是否为空来结束循环，还可以通过下面的方法：
判断有无负环：如果某个点进入队列的次数超过V次则存在负环（SPFA无法处理带负环的图）。
SPFA算法有两个优化算法 SLF 和 LLL&
SLF：Small Label First
策略，设要加入的节点是j，队首元素为i，若dist(j)&dist(i)，则将j插入队首，否则插入队尾。
LLL：Large Label Last
策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)&x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)&=x，则将i出对进行松弛操作。
SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高约 50%。
在实际的应用中SPFA的算法时间效率不是很稳定，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法。
优化之后耗时0ＭＳ，
#include&stdio.h&//SPFA
模拟队列实现最短路径
#include&string.h&
#define INF 100000
map[210][210],flag[210],Q[210],d[210];
m,n,start,tar;
& &int i,x;
& &int front=0,rear=0;
& &memset(Q,0,sizeof(Q));
& &memset(flag,0,sizeof(flag));
& &for(i=0;i&n;i++)
&d[i]=INF;
& &d[start]=0;
& &Q[rear]=start;
& &rear++;
& &flag[start]=1;
& &while(front&rear)
&x=Q[front];//出队列
&front=(front+1)%210;
&flag[x]=0;
&for(i=0;i&n;i++)
&if(d[i]&d[x]+map[x][i])
& &d[i]=d[x]+map[x][i];
& &if(!flag[i])
&Q[rear]=i;//入队列
&rear=(rear+1)%210;
&flag[i]=1;
& &if(d[tar]&INF)
&printf("%d\n",d[tar]);
& &else printf("-1\n");
& &int i,j,a,b,c;
& &while(scanf("%d%d",&n,&m)!=EOF)
&for(i=0;i&n;i++)
&for(j=0;j&n;j++)
& &map[i][j]=INF;
&for(i=0;i&m;i++)
&scanf("%d%d%d",&a,&b,&c);
&if(map[a][b]&c)
&map[a][b]=map[b][a]=c;
&scanf("%d%d",&start,&tar);
& &return 0;
其实最短路总结就一句话，不断的进行松弛操作，无论是什么解法，都要进行松弛操作，然后找到最短路径
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。2199人阅读
首先自己练习了一下实现dijkstra算法，可以把dj算法与prim算法对比记忆,要理解pre数组、min数组、V标记数组的含义！
//单源最短路径,dijkstra算法,邻接阵形式,复杂度O(n^2)
//求出源s到所有点的最短路经,传入图的顶点数n,(有向)邻接矩阵mat
//返回到各点最短距离min[]和路径pre[],pre[i]记录s到i路径上i的父结点,pre[s]=-1
//可更改路权类型,但必须非负!
//可以把dj算法与prim算法对比记忆,要理解pre数组、min数组、V标记数组的含义！
#include &iostream&
#define MAXN 200
#define inf
typedef int elem_t;
int N,M,ss,ee,ww,s,mat[MAXN][MAXN],min[MAXN],pre[MAXN];
//输出最短路径
prn_pass(int k){
if (pre[pre[k]]!=-1)
cout&&"&--"&&pre[k];
prn_pass(pre[k]);
void dijkstra(int n,elem_t mat[][MAXN],int s,elem_t* min,int* pre){
int v[MAXN],i,j,k;
for (i=0;i&n;i++)
min[i]=inf,v[i]=0,pre[i]=-1;
for (min[s]=0,j=0;j&n;j++){
for (k=-1,i=0;i&n;i++)
if (!v[i]&&(k==-1||min[i]&min[k]))
for (v[k]=1,i=0;i&n;i++)
if (!v[i]&&min[k]+mat[k][i]&min[i])
min[i]=min[k]+mat[pre[i]=k][i];
int main(){
cout&&"请输入顶点数量和边数"&&
cin&&N&&M;
for (i = 0;i & N;i++)
for (j = 0;j & N;j++)
if (i == j)
mat[i][j] = 0;
mat[i][j] =
cout&&"请输入各边起点终点和权值"&&
for (i = 0; i & M;i++)
cin&&ss&&ee&&
mat[ss][ee] =
cout&&"请输入源点"&&
dijkstra(N,mat,s,min,pre);
for (i = 0;i & N;i ++)
if (i != s)
cout&&s&&"到"&&i&&"的最短路径长度为："&&min[i]&&
cout&&"路径为："&&i;
prn_pass(i);
cout&&"&--"&&s&&
从网上看到某大牛用Floyd算法的思想也得以解决
#include &iostream&
int A[101][101];
//Floyd算法思想
int main(){
int N,i,j,k,x;
scanf("%d%d%d",&N,&a,&b);
for(i = 0;i &= N;i++)
for (j = 0;j &= N;j++)
A[i][j] = 100;
for (i = 1;i &= N;i++)
for (j = 0;j & j ++)//与第i的站相连接的有k个站，赋值为1
if ( j == 0 )
A[i][x] = 0;
else A[i][x] = 1;
for (k = 1;k &= N;k++)
for(i = 1;i &= N;i++)
for (j = 1;j &= N;j++)
if (A[i][j]&A[i][k] + A[k][j])
A[i][j] = A[i][k] + A[k][j];
if (A[a][b] & A[0][0])
cout&&A[a][b]&&
else cout&&"-1"&&
版权声明：本文为博主原创文章，未经博主允许不得转载。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：678511次
积分：9006
积分：9006
排名：第963名
原创：229篇
转载：36篇
评论：661条
(1)(9)(5)(6)(4)(19)(13)(25)(2)(13)(7)(2)(1)(1)(1)(1)(1)(4)(1)(6)(3)(2)(2)(4)(9)(11)(5)(24)(17)(1)(27)(36)(1)(2)(2)题目地址：
就是直接求最短路 &数据很弱 &什么方法都可以
#include&iostream&
int d[105][105];
void init()
for(int i=0;i&n;i++)
for(int j=0;j&n;j++)
d[i][j]=(i==j?0:INF);
2 Dijkstra
3 Bellman-Ford
4 Dijkstra priority_queue
Bellman-Ford with queue
int main()
while(cin&&n&&m)
if(n==0&&m==0)
int u,v,w;
for(int i=0;i&m;i++)
cin&&u&&v&&w;
d[u-1][v-1]=w;
d[v-1][u-1]=w;
for(int k=0;k&n;k++)
for(int i=0;i&n;i++)
for(int j=0;j&n;j++)
if(d[i][k]!=INF&&d[k][j]!=INF)d[i][j]=d[i][j]&(d[i][k]+d[k][j])?d[i][j]:(d[i][k]+d[k][j]);
cout&&d[0][n-1]&&
2 Dijkstra &赤裸裸的小白书代码
#include&iostream&
int d[105];
//} e[10005];
int done[10005];
w[105][105];
void init()
for(int i=0;i&n;i++)
d[i]=(i==0?0:INF);
memset(done, 0, sizeof(done));
for(int i=0;i&n;i++)
for(int j=0;j&n;j++)
w[i][j]=(i==j?0:INF);
2 Dijkstra
3 Bellman-Ford
4 Dijkstra priority_queue
Bellman-Ford with queue
int min(int a,int b)
return a&b?a:b;
int main()
while(cin&&n&&m)
if(n==0&&m==0)
int a,b,c;
for(int i=0;i&m;i++)
cin&&a&&b&&c;
e[i].u=a-1;
e[i].v=b-1;
w[a-1][b-1]=c;
w[b-1][a-1]=c;
// Dijkstra
for(int i=0;i&n;i++)
int m=INF;
for(int y=0;y&n;y++)
if(done[y]==0&&d[y]&=m) m=d[x=y];
done[x]=1;
for(int y=0;y&n;y++)
if(w[x][y]!=INF)
d[y]=min(d[y],d[x]+w[x][y]);
cout&&d[n-1]&&
3 Dijkstra 使用优先队列优化
记住要将无向图转化为有向图
#include&iostream&
#include&utility&
#include&vector&
#include&queue&
pair&int, int&
int d[1005];
int nxt[200010];
int first[1005];
} e[200010];
int done[1005];
w[105][105];
void init()
for(int i=0;i&n;i++)
d[i]=(i==0?0:INF);
memset(done, 0, sizeof(done));
memset(first,-1,sizeof(first));
for(int i=0;i&n;i++)
for(int j=0;j&n;j++)
w[i][j]=(i==j?0:INF);
2 Dijkstra
3 Bellman-Ford
4 Dijkstra priority_queue
Bellman-Ford with queue
int min(int a,int b)
return a&b?a:b;
int main()
while(cin&&n&&m)
if(n==0&&m==0)
int a,b,c;
for(int i=0;i&m;i++)
cin&&a&&b&&c;
e[i].u=a-1;
e[i].v=b-1;
nxt[i]=first[a-1];
first[a-1]=i;
w[a-1][b-1]=c;
w[b-1][a-1]=c;
for(int i=0;i&m;i++)
e[i+m].u=e[i].v;
e[i+m].v=e[i].u;
e[i+m].w=e[i].w;
nxt[i+m]=first[e[i].v];
first[e[i].v]=i+m;
// Dijkstra
with priority_
priority_queue&pii,vector&pii&,greater&pii& &
pq.push(make_pair(d[0], 0));
while(!pq.empty())
pii u=pq.top();
if(done[x])
done[x]=1;
for(int i=first[x];i!=-1;i=nxt[i])
int y=e[i].v;
if(d[y]&d[x]+e[i].w)
d[y]=d[x]+e[i].w;
pq.push(make_pair(d[y],y));
cout&&d[n-1]&&
}4 Bellman-Ford
#include&iostream&
#include&utility&
#include&vector&
#include&queue&
pair&int, int&
int d[1005];
} e[200010];
void init()
for(int i=0;i&n;i++)
d[i]=(i==0?0:INF);
int min(int a,int b)
return a&b?a:b;
int main()
while(cin&&n&&m)
if(n==0&&m==0)
int a,b,c;
for(int i=0;i&m;i++)
cin&&a&&b&&c;
e[i].u=a-1;
e[i].v=b-1;
for(int i=0;i&m;i++)
e[i+m].u=e[i].v;
e[i+m].v=e[i].u;
e[i+m].w=e[i].w;
//Bellman-Ford
for(int k=0;k&n-1;k++)
for(int i=0;i&2*m;i++)
int x=e[i].u;
int y=e[i].v;
if(d[x]&INF)
d[y]=min(d[y],d[x]+e[i].w);
cout&&d[n-1]&&
5 使用队列优化的Bellman-Ford (SPFA)
#include&iostream&
#include&utility&
#include&vector&
#include&queue&
int d[105];
int first[105];
int nxt[20005];
} e[20005];
void init()
for(int i=0;i&n;i++)
d[i]=(i==0?0:INF);
memset(first, -1, sizeof(first));
int min(int a,int b)
return a&b?a:b;
int main()
while(cin&&n&&m)
if(n==0&&m==0)
int a,b,c;
for(int i=0;i&m;i++)
cin&&a&&b&&c;
e[i].u=a-1;
e[i].v=b-1;
nxt[i]=first[a-1];
first[a-1]=i;
for(int i=0;i&m;i++)
e[i+m].u=e[i].v;
e[i+m].v=e[i].u;
e[i+m].w=e[i].w;
nxt[i+m]=first[e[i].v];
first[e[i].v]=i+m;
//Bellman-Ford
with_queue
queue&int&
q.push(0);
while(!q.empty())
int x=q.front();
for(int i=first[x];i!=-1;i=nxt[i])
int y=e[i].v;
if(d[y]&d[x]+e[i].w)
d[y]=d[x]+e[i].w;
if(!inq[y])
q.push(y);
cout&&d[n-1]&&
需要注意的是 &因为SPFA能处理负权&#20540; &，所以 关键是 &踢出队列以后 &把在inq这个标记清除了
和在Dijkstra 中， &踢出队列仍然不用做任何操作
只需要维护done数组 ，已经做过就不要再进队 出队了（出队就是“进入A集合”） &然后更新后重新进入优先队列 &因为只要进入 &优先级一定比更新之前的那个pair高 &那么一定会先完成done[x]=1 操作 ，没有扔掉的也无所谓了。
如果不喜欢向前星 &用vector邻接表也行
这里还是全部重新用vector 打一遍
1用pq 维护的DIjkstra & & 使用vector版本
(注： 需要说明的是 ，这里的队列和SPFA里的队列完全不同 ，这里仅仅是取出当前d&#20540;最小的快速方法而SPFA里面的队列是是为了BFS)
#include&iostream&
#include&vector&
#include&utility&
#include&queue&
typedef pair&int,int&
#define INF
int d[105];
int done[105];
vector&int& G[1000];
vector&int& E[1000];
int min(int a,int b)
return a&b?a:b;
void init()
for(int i=0;i&n;i++)
d[i]=(i==0?0:INF);
for(int i=0;i&n;i++)
// 取代前向星
G[i].clear();
E[i].clear();
memset(done, 0, sizeof(done));
int main()
while(cin&&n&&m)
if(n==0&&m==0)
int u,v,w;
for(int i=0;i&m;i++)
cin&&u&&v&&w;
G[u-1].push_back(v-1);
G[v-1].push_back(u-1);
E[u-1].push_back(w);
E[v-1].push_back(w);
// Dijkstra with priority_queue
priority_queue&pii,vector&pii&,greater&pii& &
pq.push(make_pair(d[0], 0));
while(!pq.empty())
pii u=pq.top();
if(done[x])
done[x]=1;
int s=G[x].size();
for(int i=0;i&s;i++)
int y=G[x][i];
if(d[x]+E[x][i]&d[y])
d[y]=d[x]+E[x][i];
pq.push(make_pair(d[y],y));
cout&&d[n-1]&&
2 SPFA & vector版本
#include&iostream&
#include&vector&
#include&queue&
#define INF
int d[105];
int inq[105];
vector&int& G[105];
vector&int& E[105];
void init()
for(int i=0;i&n;i++)
d[i]=(i==0?0:INF);
memset(inq, 0, sizeof(inq));
for(int i=0;i&n;i++)
G[i].clear();
E[i].clear();
int min(int a,int b)
return a&b?a:b;
int main()
while(cin&&n&&m)
if(n==0&&m==0)
int u,v,w;
for(int i=0;i&m;i++)
cin&&u&&v&&w;
G[u-1].push_back(v-1);
G[v-1].push_back(u-1);
E[u-1].push_back(w);
E[v-1].push_back(w);
for(int i=0;i&m;i++)
e[i+m].u=e[i].v;
e[i+m].v=e[i].u;
e[i+m].w=e[i].w;
queue&int&
q.push(0);
while(!q.empty())
int x=q.front();
int s=G[x].size();
for(int i=0;i&s;i++)
int y=G[x][i];
if(d[y]&d[x]+E[x][i])
d[y]=d[x]+E[x][i];
if(!inq[y])
q.push(y);
cout&&d[n-1]&&
版权声明：本文为博主原创文章，未经博主允许不得转载。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：102409次
积分：3491
积分：3491
排名：第4859名
原创：258篇
评论：15条
(28)(72)(48)(8)(1)(1)(1)(36)(18)(48)(2)您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
最短路问题Dijkstra算法.ppt17页
本文档一共被下载：
次 ,您可免费全文在线阅读后下载本文档
文档加载中...广告还剩秒
需要金币：70 &&
最短路问题Dijkstra算法.ppt
你可能关注的文档：
··········
··········
一、网络无负权的最短路 Dijkstra算法基本思想 计算实例： * 10.3
最短路问题 最短路问题是网络理论中应用最广泛的问题之一. 许多优化问题可以使用这个模型．如设备更新、管道铺设、线路安排、厂区布局等. 我们曾介绍了最短路问题的动态规划解法，但某些最短路问题 如道路不能整齐分段者 构造动态规划方程比较困准、而图论方法则比较有效。 最短路问题：在一个赋权图G上，给定两个顶点u和 v，在所有连接顶点u和 v 的路中，寻找路长最短的路（称为u和 v最短路.）
u和 v最短路的路长也称为u和 v的距离-d u,v . 有些最短路问题也可以求网络中某指定点到其余所有结点的最短路、或求网络中任意两点间的最短路. 本算法由Dijkstra于1959年提出，可用于求解指定两点间的最短路，或从指定点到其余各点的最短路，目前被认为是求无负权网络最短路问题的最好方法。 算法的基本思路基于以下原理： 若序列vs ,v1 ,…,vn是从vs到vn的最短路， 则序列vs ,v1 ,…,vn-1必为从vs到vn-1的最短路。 ――Dijkstra算法 Dijkstra算法的基本思想是从vs出发，逐步地向外探寻最短路，采用标号法。 执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从vs到该点的最短路长（称为P标号），或者是从vs到该点的最短路长的上界（称为T标号）。 算法每一步都把某个顶点的T 标号改为P 标号， 当终点vt 得到 P 标号时，计算结束。最多n-1步。 求连接 vs、vt 的最短路. - 0 ∞ - ∞ - T P ∞ - ∞ - ∞ - ∞ - 开始，给vs以 P 标号，P vs
0, 其余各点给 T 标号 T vi
+∞. 2 2 7 4 1 4 7 3 1 5 5 5 vs v2 v1 vt v4 v5 v3 Step 1:
Dijkstra算法基本步骤： - 0 ∞ - ∞ - ∞ - ∞ - ∞ - ∞ - 若 vi 为刚得到 P 标号的点,考虑这样的点 vj :
vi ,vj ∈E 且
正在加载中，请稍后...