单源最短路问题-白红宇

单源最短路问题

阅读量：5071 次

发布时间：2019-06-12

本文共 5066 字，大约阅读时间需要 16 分钟。

1.bellman-ford

1 #include
      
        2 #define INF 1000000 3 using namespace std; 4 struct edge 5 { 6     int from,to,cost; 7     edge(){} 8     edge(int ff,int tt,int cc) 9     {10         from=ff;11         to=tt;12         cost=cc;13     }14 };15 const int maxn=105;16 const int maxe=10005;17 int d[maxn];18 edge es[maxe];19 int v,e;20 21 void bellman_ford(int s)22 {23     fill(d,d+v,INF);24     d[s]=0;25     while(true)26     {27         bool update=false;28         for(int i=0;i
       
        d[e.from]+e.cost)32             {33                 d[e.to]=d[e.from]+e.cost;34                 update=true;35             }36         }37         if(!update) break;38     }39     for(int i=0;i
        
         d[e.from]+e.cost)54             {55                 d[e.to]=d[e.from]+e.cost;56 57                 //如果第n次仍然更新了，则存在负圈58                 if(i==v-1) return true;59             }60         }61     }62     return false;63 }64 int main()65 {66     cin>>v>>e;67     int from,to,cost;68     for(int i=0;i
         
          >from>>to>>cost;71         from--;72         to--;73         es[i]=edge(from,to,cost);74     }75     //cout<

View Code

2.dijkstra

1 #include
      
        2 #define INF 1000000 3 using namespace std; 4 const int maxn=1010; 5 //邻接矩阵形式 6 int cost[maxn][maxn]; 7 int used[maxn]; 8 int d[maxn]; 9 int n;10 int prev[maxn];//最短路上所有前驱结点11 vector
       
         get_path(int t)12 {13     vector
        
          path;14     for(;t!=-1;t=prev[t])15         path.push_back(t);//不断沿着prev[t]走直到t=s16     reverse(path.begin(),path.end());17     return path;18 }19 void dijkstra(int s)20 {21     fill(d,d+n,INF);22     fill(used,used+n,0);23     fill(prev,prev+n,-1);24     d[s]=0;25     while(true)26     {27         int v=-1;28         for(int u=0; u
         
          d[v]+cost[v][u])40             {41                 d[u]=d[v]+cost[v][u];42                 prev[u]=v;43             }44         }45     }46     for(int i=0; i

path=get_path(n-1);52 for(int i=0;i

>n;61 for(int i=0; i

>cost[i][j];66 }67 }68 dijkstra(0);69 return 0;70 }71 /*72 测试数据教科书 P189 G6 的邻接矩阵其中数字 1000000 代表无穷大73 674 1000000 1000000 10 100000 30 10075 1000000 1000000 5 1000000 1000000 100000076 1000000 1000000 1000000 50 1000000 100000077 1000000 1000000 1000000 1000000 1000000 1078 1000000 1000000 1000000 20 1000000 6079 1000000 1000000 1000000 1000000 1000000 100000080 结果：81 D[0] D[1] D[2] D[3] D[4] D[5]82 0 1000000 10 50 30 6083 */

View Code

3.堆优化的dijkstra

1 #include
      
        2 #include
       
         3 #include
        
          4 #define INF 1000000 5 using namespace std; 6 typedef pair
         
           P; //first代表最短距离，second代表顶点的编号 7 //邻接表 8 struct edge 9 {10     int to,cost;11     edge(int tt,int cc)12     {13         to=tt;14         cost=cc;15     }16 };17 const int maxn=105;18 vector
          
            G[maxn];19 int d[maxn];20 int n;21 void heap_dijkstra(int s)22 {23     fill(d,d+n,INF);24     priority_queue
           
            ,greater
             > que;25 que.push(P(0,s));26 d[s]=0;27 while(!que.empty())28 {29 P p=que.top();30 que.pop();31 int v=p.second;32 if(p.first>d[v]) continue;33 for(int i=0;i
             
              d[v]+e.cost)37 {38 d[e.to]=d[v]+e.cost;39 que.push(P(d[e.to],e.to));40 }41 }42 }43 for(int i=0;i
              
               >n;49 int from,to,cost;50 for(int i=0;i
               
                >from>>to>>cost;53 from--;54 to--;55 G[from].push_back(edge(to,cost));56 G[to].push_back(edge(from,cost));57 }58 59 heap_dijkstra(0);60 return 0;61 }

View Code

4.floyd_warshall

1 #include
      
        2 #include
       
         3 #define INF 1000000 4 using namespace std; 5 const int maxn=105; 6 int d[maxn][maxn]; 7 int n; 8 //任意两点间的最短路问题,dp 9 void floyd_warshall()10 {11     for(int i=0; i
        
         >n;26     for(int i=0; i
         
          >d[i][j];29 30     floyd_warshall();31     return 0;32 }

View Code

5.spfa

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 #define inf 99999999 7 typedef struct dd 8 { 9     int a,d;10 }node;11 int dis[20005],n;12 vector
          
            maps[20005];13 void sets()14 {15     for(int i=1;i<=n;i++)16     {17         dis[i]=inf;18     }19 }20 void spfa()21 {22     queue
           
             q;23 int b[20005]={ 0},t;//b数组标识节点是否在队列中24 q.push(1);//起点入队25 b[1]=1; //标记26 dis[1]=0; //距离27 while(!q.empty())28 {29 //队首元素出队30 t=q.front();31 q.pop();32 //标记33 b[t]=0;34 //这个点作为起点的路径有多少35 int len=maps[t].size();36 int a;37 for(int i=0;i
            
             maps[t][i].d+dis[t])42 {43 dis[a]=maps[t][i].d+dis[t];44 if(!b[a])45 {46 b[a]=1;47 q.push(a);48 }49 }50 }51 }52 }53 int main()54 {55 int m,a,b,l;56 node Now;57 while(scanf("%d%d",&n,&m)==2)58 {59 sets();60 while(m--)61 {62 scanf("%d%d%d",&a,&b,&l);63 Now.a=b;64 Now.d=l;65 maps[a].push_back(Now);66 }67 spfa();68 for(int i=2;i<=n;i++)69 {70 printf("%d\n",dis[i]);71 }72 }73 return 0;74 }

View Code

转载于:https://www.cnblogs.com/wangkaipeng/p/6442491.html

你可能感兴趣的文章