首页 > 代码库 > 最短路径算法学习总结

最短路径算法学习总结

2024-07-12 15:03:08   215人阅读

Dijkstra最短路径算法：

dijkstra 算法的优点在于可以求出从一点到所有其他点的最短距离；

input：

5 7
1 2 10
1 3 20
1 5 30
2 5 10
2 3 5
4 5 20
4 3 30

output:

0 10 15 40 20//这是求的在这颗树中，1到所有点的最短距离

 1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 const int N=1100; 5 const int INF=1000000;  6 int map[N][N]; 7 //int p[N]; 8 int vis[N]; 9 int low[N];10 int n,m;//代表点的个数和路线的数量 11 void Dijkstra(int s)12 {13     for(int i=1;i<=n;i++)14     {15     low[i]=map[s][i];16     }17     low[s]=0;18     vis[s]=-1;19     int v;20     for(int i=1;i<n;i++)21     {22         int Min=INF;23         for(int j=1;j<=n;j++)24         {25             if(vis[j]!=-1&&low[j]<Min)26             {27                 Min=low[j];28                 v=j;29             }30         }31         vis[v]=-1;32         for(int j=1;j<=n;j++)33         {34             if(vis[j]!=-1&&low[j]>low[v]+map[j][v])35             low[j]=low[v]+map[j][v];//不断更新两点间的最短距离 36         }37     }38 }39 int main()40 {41     while(cin>>n>>m)42     {43         //memset(map,0,sizeof(map));44         for(int i=1;i<=n;i++)45         for(int j=1;j<=n;j++)46         map[i][j]=INF;47         memset(vis,0,sizeof(vis));48         int a,b,c;49         for(int i(1);i<=m;i++)50         {51         scanf("%d %d %d",&a,&b,&c);52         map[a][b]=map[b][a]=c;53         }54         Dijkstra(1);55         for(int i=1;i<=n;i++)56         {57             cout<<low[i]<<" ";58         }59         cout<<endl;60     }61     return 0;62 }

floyd算法:

floyd算法比较费空间和时间，不适合处理大量数据；

 1 #include<iostream>  2 using namespace std; 3 const int N=300;//这个地方不应该定义的太大，不然会报错 4 const int INF=11111111; 5 int main() 6 { 7     int dis[N][N]; 8     int n,m;//分别代表点的数量和路线的条数  9     while(cin>>n>>m)10     {11         for(int i=1;i<=n;i++)12         for(int j=1;j<=n;j++)13         dis[i][j]=INF;14         for(int i=1;i<=n;i++)15         dis[i][i]=0;16         int a,b,c;17         for(int i=1;i<=m;i++)18         { 19             scanf("%d %d %d",&a,&b,&c);20             if(dis[a][b]>c)21             dis[a][b]=dis[b][a]=c;22         }23         for(int k=1;k<=n;k++)24         for(int i=1;i<=n;i++)25         {26             for(int j=i+1;j<=n;j++)27             {28                 if(dis[i][k]!=INF&&dis[k][j]!=INF&&dis[i][j]>dis[i][k]+dis[k][j])29                 dis[j][i]=dis[i][j]=dis[i][k]+dis[k][j];30             }31         }32         int w,u;33         scanf("%d %d",&w,&u);34         if(dis[u][w]==INF)printf("no solution\n");35         else printf("%d\n",dis[u][w]);36     }37     return 0;38 }


联系
我们