图结构练习——最短路径

图结构练习——最短路径

Time Limit: 1000ms   Memory limit: 65536K  有疑问？点这里^_^

题目描述

 给定一个带权无向图，求节点1到节点n的最短路径。  

输入

 输入包含多组数据，格式如下。 第一行包括两个整数n m，代表节点个数和边的个数。(n<=100) 剩下m行每行3个正整数a b c，代表节点a和节点b之间有一条边，权值为c。  

输出

 每组输出占一行，仅输出从1到n的最短路径权值。（保证最短路径存在）  

示例输入

3 2 1 2 1 1 3 1 1 0

示例输出

1 0

提示

  #include<iostream> #include<limits.h> #include<cstring> #define Max INT_MAX #define MaxS 110 using namespace std; int gp[MaxS][MaxS]; int dist[MaxS]; //原点v0到vi最短路径长度 int path[MaxS]; //前一序号节点 int n,m; void Dijkstra() { int v[MaxS]; for(int i=1; i<=n; i++) { dist[i]=gp[1][i]; if(i!=1&&dist[i]<Max) path[i]=1; else path[i]=-1; } memset(v,0,sizeof(v)); v[1]=1; dist[1]=0; for(int i=2; i<=n; i++) { int Min=Max; int k=1; for(int j=1; j<=n; j++) if(!v[j]&&dist[j]<Min) { Min=dist[j]; k=j; } v[k]=1; for(int j=1; j<=n; j++) if(!v[j]&&gp[k][j]<Max&&dist[k]+gp[k][j]<dist[j]) { dist[j]=dist[k]+gp[k][j]; path[j]=k; } } } int main() { while(cin>>n>>m) { int a,b,c; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) if(i==j) gp[i][j]=0; else gp[i][j]=Max; for(int i=0; i<m; i++) { cin>>a>>b>>c; if(gp[a][b]>c) gp[a][b]=gp[b][a]=c; } Dijkstra(); cout<<dist[n]<<endl; } return 0; }

几乎所有的最短路算法其步骤都可以分为两步

1.初始化

2.松弛操作

初始化： d数组全部赋值为INF（无穷大）；p数组全部赋值为s（即源点），或者赋值为-1，表示还没有知道前驱

             然后d[s]=0;  表示源点不用求最短路径，或者说最短路就是0。将源点入队；

　　　　（另外记住在整个算法中有顶点入队了要记得标记vis数组，有顶点出队了记得消除那个标记）

队列+松弛操作

读取队头顶点u，并将队头顶点u出队（记得消除标记）；将与点u相连的所有点v进行松弛操作，如果能更新估计值（即令d[v]变小），那么就更新，另外，如果点v没有在队列中，那么要将点v入队（记得标记），如果已经在队列中了，那么就不用入队

以此循环，直到队空为止就完成了单源最短路的求解

基于BFS的SPFA算法： #include<iostream> #include<queue> #include<cstring> #include<limits.h> #define Max INT_MAX #define MaxN 110 using namespace std; struct node { int to; int we; node *next; } *lis[MaxN]; int path[MaxN],dist[MaxN]; int n,m; void SPFA_BFS(int v0) { int v[MaxN]; for(int i=0; i<n; i++) { dist[i]=Max; path[i]=v0; v[i]=0; } dist[v0]=0; v[v0]++; queue<int >q; q.push(v0); while(!q.empty()) { int t=q.front(); q.pop(); v[t]--; node *tmp=lis[t]; while(tmp) { int k=tmp->to; if(dist[t]+tmp->we<dist[k]) { dist[k]=dist[t]+tmp->we; path[k]=t; if(!v[k]) { q.push(k); v[k]++; } } tmp=tmp->next; } } } int main() { while(cin>>n>>m) { int a,b,c; memset(lis,0,sizeof(lis)); for(int i=0; i<m; i++) { cin>>a>>b>>c; a--; b--; node *p=new node; p->we=c; p->to=b; p->next=lis[a]; lis[a]=p; node *q=new node; q->we=c; q->to=a; q->next=lis[b]; lis[b]=q; } SPFA_BFS(0); cout<<dist[n-1]<<endl; } return 0; } 基于DFS的SPFA算法（时间复杂度高）： #include<iostream> #include<queue> #include<cstring> #include<limits.h> #define Max INT_MAX #define MaxN 110 using namespace std; struct node {     int to;     int we;     node *next; } *lis[MaxN]; int path[MaxN],dist[MaxN]; int n,m; int vb[MaxN]; int  SPFA_DFS(int u) {     vb[u]=1;     node *p=lis[u];     while(p)     {         int t=p->to;         int k=p->we;         if(dist[u]+k<dist[t])         {             dist[t]=dist[u]+k;             if(!vb[t])             {                 if(SPFA_DFS(t))                     return 1;             }             else return 1;         }         p=p->next;     }     vb[u]=0;     return 0; } int main() {     while(cin>>n>>m)     {         int a,b,c;         memset(lis,0,sizeof(lis));         for(int i=0; i<m; i++)         {             cin>>a>>b>>c;             a--;             b--;             node *p=new node;             p->we=c;             p->to=b;             p->next=lis[a];             lis[a]=p;             node *q=new node;             q->we=c;             q->to=a;             q->next=lis[b];             lis[b]=q;         }         memset(vb,0,sizeof(vb));         for(int i=1; i<n; i++)             dist[i]=Max;         dist[0]=0;         SPFA_BFS(0);         cout<<dist[n-1]<<endl;     }     return 0; }