首页 > 代码库 > dijkstra，SPFA，Floyd求最短路
dijkstra，SPFA，Floyd求最短路
Dijkstra：
裸的算法，O(n^2)，使用邻接矩阵：
算法思想：
定义两个集合，一开始集合1只有一个源点，集合2有剩下的点。
STEP1：在集合2中找一个到源点距离最近的顶点k：min{d[k]}
STEP2：把顶点k加入集合1中，同时修改集合2中的剩余顶点j的d[j]是否经过k之后变短，若变短则修改d[j];
if d[k]+a[k,j]<d[j] then d[j]=d[k]+a[k,j];
STEP3：重复STEP1，直到集合2为空为止。
#include <iostream>#include <cstring>using namespace std;#define MAXINT 9999999int minx,minj,x,y,t,k,n,m,tmp;int v[1000],d[1000],a[1000][1000];int main(){ cin>>n>>m>>k; memset(a,0,sizeof(a)); memset(d,MAXINT,sizeof(d)); memset(v,0,sizeof(v)); d[k]=0; for (int i=1;i<=m;i++) { cin>>x>>y>>t; a[x][y]=t; a[y][x]=t; } for (int i=1;i<=n-1;i++) { minx=MAXINT; for (int j=1;j<=n;j++) if ((v[j]==0)&&(d[j]<minx)) { minx=d[j]; minj=j; } v[minj]=1; for (int j=1;j<=n;j++) if ((v[j]==0)&&(a[minj][j]>0)) { tmp=d[minj]+a[minj][j]; if (tmp<d[j]) d[j]=tmp; } } for (int i=1;i<=n;i++) cout<<d[i]<<" "; cout<<endl; return 0;}
Tips：上述STEP1可以用优先队列优化。
模版：
（使用邻接表，Reference：http://www.cnblogs.com/qijinbiao/archive/2012/10/04/2711780.html）
eg：邻接表
i：某条边的起点 eg[i][j].x：从点i出发的第j条边的终点 eg[i][j].d：这条边的距离
#include <iostream>#include <cstdio>#include <queue>#include <vector>using namespace std;const int Ni = 10000;const int INF = 1<<27;struct node{ int x,d; node(){} node(int a,int b){x=a;d=b;} bool operator < (const node & a) const { if(d==a.d) return x<a.x; else return d > a.d; }};vector<node> eg[Ni];int dis[Ni],n;void Dijkstra(int s){ int i; for(i=0;i<=n;i++) dis[i]=INF; dis[s]=0; priority_queue<node> q; q.push(node(s,dis[s])); while(!q.empty()) { node x=q.top();q.pop(); for(i=0;i<eg[x.x].size();i++) { node y=eg[x.x][i]; if(dis[y.x]>x.d+y.d) { dis[y.x]=x.d+y.d; q.push(node(y.x,dis[y.x])); } } }}int main(){ int a,b,d,m,k; scanf("%d%d%d",&n,&m,&k); for(int i=0;i<=n;i++) eg[i].clear(); while(m--) { scanf("%d%d%d",&a,&b,&d); eg[a].push_back(node(b,d)); eg[b].push_back(node(a,d)); } Dijkstra(k); for (int i=1;i<=n;i++) printf("%d\n",dis[i]); return 0;}
STL优先队列Reference：http://www.cnblogs.com/wanghetao/archive/2012/05/22/2513514.html
SPFA：
即用队列优化过的Bellman-Ford
( Reference:http://blog.csdn.net/niushuai666/article/details/6791765 )
Pascal代码...
var q,d:array[1..1000] of longint; a:array[1..1000,1..1000] of longint; visited:array[1..1000] of boolean; head,tail,s,n,dt,i,j:longint;beginassign(input,‘spfa.in‘);reset(input);fillchar(d,sizeof(d),127 div 3);fillchar(visited,sizeof(visited),false);fillchar(a,sizeof(a),0);readln(s);d[s]:=0;readln(n);for i:=1 to n do for j:=1 to n do begin read(dt); a[i,j]:=dt; a[j,i]:=dt;{ if dt<>0 then begin if i=s then d[j]:=dt; if j=s then d[i]:=dt; end; } end;head:=0;q[1]:=s;visited[s]:=true;tail:=1;while head<tail do begin inc(head); visited[q[head]]:=false; for i:=1 to n do begin if (a[q[head],i]>0) and (d[q[head]]+a[q[head],i]<d[i]) then begin d[i]:=d[q[head]]+a[q[head],i]; if not visited[i] then begin inc(tail); q[tail]:=i; visited[i]:=true; end; end; end; end;for i:=1 to n do write(d[i],‘ ‘);writeln;close(input);end.
Floyd：
多源最短路
//path[i,j]：用来输出最短路径//floydvar path,d:array[1..1000,1..1000] of longint; n,k,i,j,st,en,x,y,tmp:longint;procedure dfs(i,j:longint);beginif path[i,j]>0 then begin dfs(i,path[i,j]); write(path[i,j],‘->‘); dfs(path[i,j],j); end;end;beginassign(input,‘floyd.in‘);reset(input);fillchar(d,sizeof(d),127 div 3);readln(n);for i:=1 to n do d[i,i]:=0;for i:=1 to n do for j:=1 to n do path[i,j]:=-1;readln(st,en);while not eof do begin readln(x,y,tmp); d[x,y]:=tmp; d[y,x]:=tmp; path[x,y]:=0; path[y,x]:=0; end;for k:=1 to n do for i:=1 to n do for j:=1 to n do begin if d[i,k]+d[k,j]<d[i,j] then begin d[i,j]:=d[i,k]+d[k,j]; path[i,j]:=k; end; end;writeln(d[st,en]);write(st,‘->‘);dfs(st,en);writeln(en);close(input);end.
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。