图论-最短路径-Dijkstra

单源、无负权（会出现负值圈）可打印路径的模版：O(n^2)

Dijkstra求解是一个点一旦已经访问了，后续即使有从起点到该点更短的路径，也无法更新了。所以不适合有负权的图。如下图：1->2的最短路径应该是1->3->2,而不是1->2。实质：贪心

  1. #include <bits/stdc++.h>  
  2. using namespace std;  
  3. const int maxn = 10000;  
  4. const int inf = 1e9;  
  5. int n, G[maxn][maxn], m;//n个点，m条边  
  6. int dis[maxn], path[maxn];  
  7. bool vis[maxn]={false};  
  8. void Dijkstra(int s)  
  9. {  
  10.     for(int i = 0; i < n; i++)  
  11.     {  
  12.         dis[i] = G[s][i];  
  13.         if(G[s][i] != inf) path[i] = s;  
  14.         else path[i] = -1;  
  15.     }  
  16.     dis[s] = 0;//起点距离自身为0  
  17.     for(int i = 0; i < n; i++)//循环n次，或者令vis[s]=1，循环n-1次  
  18.     {  
  19.         int u = -1, minn = inf;  
  20.         for(int j = 0; j < n; j++)  
  21.         {  
  22.             if(!vis[j] && dis[j] < minn)  
  23.             {  
  24.                 u = j;  
  25.                 minn = dis[j];//找未访问过的最短的距离  
  26.             }  
  27.         }  
  28.         if(u == -1) break;//不连通  
  29.         vis[u] = true;  
  30.         for(int v = 0; v < n; v++)  
  31.         {  
  32.             //从该点出发更新其他点到起点的距离  
  33.             if(!vis[v] && dis[u] + G[u][v] < dis[v])  
  34.             {  
  35.                 dis[v] = dis[u] + G[u][v];  
  36.                 path[v] = u;//可输出路径  
  37.             }  
  38.         }  
  39.     }  
  40. }  
  41. void displayPath(int e)  
  42. {  
  43.     vector<int> p;  
  44.     printf("0-->%d 距离：%d\n路径为：",e, dis[e]);  
  45.     p.push_back(e);  
  46.     int pre = path[e];  
  47.     while(pre != -1)  
  48.     {  
  49.         p.push_back(pre);  
  50.         pre = path[pre];  
  51.     }  
  52.     for(int i = p.size() - 1; i >0; i--)  
  53.         printf("%d-->", p[i]);  
  54.     printf("%d\n", p[0]);  
  55. }  
  56. int main()  
  57. {  
  58.     freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);  
  59.     ios::sync_with_stdio(false);  
  60.     cin.tie(nullptr);  
  61.     cout.tie(nullptr);  
  62.     cin >> n >> m;  
  63.     int x, y, z;  
  64.     fill(G[0],G[0]+maxn*maxn,inf);//全都初始化不可达到  
  65.     for(int i = 0; i < m; i++)  
  66.     {  
  67.         cin >> x >> y >> z;  
  68.         G[x][y] = G[y][x] = z;  
  69.     }  
  70.     Dijkstra(0);  
  71.     for(int i = 0; i < n; i++)  
  72.         displayPath(i);  
  73.     return 0;  
  74. }  

图论-最短路径-Floyd

多源，无环，无负权：O(n^3)  实质：动态规划

 

再考虑顶点2和3，更新距离和路径

路径的求解原理：

路径的求解：

  1. #include <bits/stdc++.h>  
  2. using namespace std;  
  3. const int maxn = 10000;  
  4. const int inf = 1e9;  
  5. int n,m;  
  6. int dis[maxn][maxn], path[maxn][maxn], edges[maxn][maxn];  
  7. void Floyd()  
  8. {  
  9.     for(int i = 0; i < n; i++)  
  10.     {  
  11.         for(int j = 0; j < n; j++)  
  12.         {  
  13.             if(i == j) dis[i][j] = 0;//i==j需要特殊处理一下  
  14.             else dis[i][j] = edges[i][j];  
  15.             //注意i ！= j，因为是多源，不能像Dijkstra那样把起点的path设成-1  
  16.             if(i != j && dis[i][j] != inf) path[i][j] = i;  
  17.             else path[i][j] = -1;  
  18.         }  
  19.     }  
  20.     for(int k = 0; k < n; k++)  
  21.     {  
  22.         for(int i = 0; i < n; i++)  
  23.         {  
  24.             for(int j = 0; j < n; j++)  
  25.             {  
  26.                 if(dis[i][k] + dis[k][j] < dis[i][j])  
  27.                 {  
  28.                     dis[i][j] = dis[i][k] + dis[k][j];  
  29.                     path[i][j] = path[k][j];  
  30.                 }  
  31.             }  
  32.         }  
  33.     }  
  34. }  
  35. int main()  
  36. {  
  37.     //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);  
  38.     ios::sync_with_stdio(false);  
  39.     cin.tie(nullptr);  
  40.     cout.tie(nullptr);  
  41.     cin >> n >> m;  
  42.     int x, y, z;  
  43.     fill(edges[0],edges[0]+maxn*maxn,inf);//全都初始化不可达到  
  44.     for(int i = 0; i < m; i++)  
  45.     {  
  46.         cin >> x >> y >> z;  
  47.         edges[x][y] = edges[y][x] = z;  
  48.     }  
  49.     Floyd();  
  50.     for(int i = 0; i < n; i++)  
  51.         printf("dis[0][%d]: %d\n", i, dis[0][i]);  
  52.     return 0;  
  53. }  

图论-最短路径-SPFA(队列优化的Bellman-Ford)

不适合负权回路的图，单源最短路：O(e)-O(ne) e为边数

  1. #include <bits/stdc++.h>  
  2. using namespace std;  
  3. const int maxn = 10000;  
  4. const int inf = 1e9;  
  5. int n,m;  
  6. int dis[maxn], path[maxn], vis[maxn];  
  7. struct node{  
  8.     int Next,val;  
  9. };  
  10. vector<node> edges[maxn];  
  11. queue<int> q;  
  12. void spfa(int s)  
  13. {  
  14.     for(int i = 0; i < n; i++)  
  15.     {  
  16.         dis[i] = inf;  
  17.         path[i] = -1;  
  18.     }  
  19.     dis[s] = 0;//自己到自己0  
  20.     vis[s] = 1;  
  21.     q.push(s);  
  22.     while(!q.empty())  
  23.     {  
  24.         int u = q.front();  
  25.         q.pop();  
  26.         vis[u] = 0;  
  27.         for(int i = 0; i < edges[u].size(); i++)//松弛和自己相邻的边  
  28.         {  
  29.             int v = edges[u][i].Next, weight = edges[u][i].val;  
  30.             if(dis[u] + weight < dis[v])  
  31.             {  
  32.                 dis[v] = dis[u] + weight;  
  33.                 path[v] = u;  
  34.                 if(!vis[v])  
  35.                 {  
  36.                     vis[v] = 1;  
  37.                     q.push(v);  
  38.                 }  
  39.             }  
  40.         }  
  41.     }  
  42. }  
  43. int main()  
  44. {  
  45.     //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);  
  46.     ios::sync_with_stdio(false);  
  47.     cin.tie(nullptr);  
  48.     cout.tie(nullptr);  
  49.     cin >> n >> m;  
  50.     int x, y, z;  
  51.     for(int i = 0; i < m; i++)  
  52.     {  
  53.         cin >> x >> y >> z;  
  54.         edges[x].push_back({y,z});  
  55.         edges[y].push_back({x,z});  
  56.     }  
  57.     spfa(0);  
  58.     for(int i = 0; i < n; i++)  
  59.         printf("dis[%d]:%d\n",i, dis[i]);  
  60.     return 0;  
  61. }