三个最短路算法

最短路径算法

Floyed-Warshall O(N3)

算法描述：
    a.初始化：如果点u,和v有相连的边则第dis[u][v] = dis[v][u] = distance;
    如果不相连则等于无穷大。
    
    b.核心代码 (实用于负的权值)
        ```
  1         for (int k = 1; k <= n; ++ k)
  2             for (int i = 1; i <= n; ++ i)
  3                 for (int j = 1; j <= n; ++ j)
  4                     if (dis[i][j] > dis[i][k] + dis[k][j])
  5                         dis[i][j] = dis[i][k] + dis[k][j];
        ```
        
    c.算法思想分析
        三层循环，第一层循环中点k， 第二层，第三层循环起点和终点；
        如果点i到点看的距离加上点k到点j的距离小于原先得的距离，这跟新最短距离。

Dijkstra O(N2)

是一种从一个点计算到所有点的最短距离的一种算法。
直接附上代码理解；

题目 D ：旅游规划时间限制：1 sec 内存限制：128 MB 提交：6 正确：2

题目描述有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

输入输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N?1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。

输出在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

样例输入

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

样例输出

3 40

  1 #include <cstring>
  2 #include <algorithm>
  3 #define INF 0x3f3f3f3f
  4 using namespace std;
  5 
  6 constexpr size_t maxn = 505;
  7 
  8 int dt[maxn][maxn];
  9 int dis[maxn];
 10 int cost[maxn];
 11 int dcost[maxn][maxn];
 12 bool vis[maxn];
 13 
 14 int main()
 15 {
 16  int n, m, s, d;
 17  cin >> n >> m >> s >> d;
 18 
 19  for (int i = 0; i < n; ++ i)
 20      for (int j = 0; j < n; ++ j)
 21          dt[i][j] = dcost[i][j] = INF;
 22 
 23  for (int i = 0; i < m; ++ i)
 24  {
 25      int a, b, c, d;
 26      cin >> a >> b >> c >> d;
 27      dt[a][b] = dt[b][a] = c;
 28      dcost[a][b] = dcost[b][a] = d;
 29  }
 30 
 31  for (int i = 0; i < n; ++ i)
 32  {
 33      dis[i] = dt[i][s];
 34      cost[i] = dcost[i][s];
 35  }
 36  dis[s] = 0; vis[s] = true;
 37  int Md, v0;
 38  v0 = s;
 39  //Dijkstra O(N2)
 40  for (int i = 0; i < n; ++ i)
 41  {
 42      Md = INF;
 43      for (int j = 0; j < n; ++ j)
 44      {
 45          if (!vis[j])
 46              if(dis[j] < Md)
 47              {
 48                  Md = dis[j];
 49                  v0 = j;
 50              }
 51      }
 52 
 53  vis[v0] = true;
 54 
 55  for (int i = 0; i < n; ++ i)
 56  {
 57      if (!vis[i] && Md + dt[v0][i] < dis[i]){
 58          dis[i] = Md + dt[v0][i];
 59          cost[i] = cost[v0] + dcost[v0][i];
 60      }
 61      else if (!vis[i] && Md + dt[v0][i] == dis[i] && cost[i] > dcost[v0][i] + cost[v0]){
 62          cost[i] = cost[v0] + dcost[v0][i];
 63      }
 64  }
 65 }
 66  cout << dis[d] << " " << cost[d] << endl;
 67  return 0;
 68 }
 69

起点为s，dis[v]表示s->v的最短距离，pre[v]为v的前驱，可以用来输出路径。

Bellman-Ford O(NE)（只能处理存在负权的最短路径问题不，无法解决负权回路问题）

是用来计算从一个点到其它点的最短距离的算法，和Dijkstra一样是以种单元最短路径算法。

时间复杂度：O（NE）N是顶点数，E是变得数。
算法实现：
    设s为起点，dis[v]是s到v的最短距离，pre[v]是v的前驱，w[j] 是边j的长度，且j连接u，v。
初始化；dis[s] = 0, dis[v] = 无穷, pre[s] = 0;
核心代码：
```
  1     for (i = 1; i <= n - 1; ++ i)
  2         for (j = 1; j <= E; ++ j) //要枚举所有的边，不是点。
  3             if(dis[u] + w[j] < dis[v]) // u, v 是这条边连接的两个点。
  4             {
  5                 dis[v] = dis[u] + w[j];
  6                 pre[v] = u;
  7             }
```
算法分析&思路：
    一开始认为起点是白点（dis[1] = 0），每一次都枚举所有的边，必然会有一些边，连接着白点和蓝点，
    因此，每次都能用所有的白点去修改所有的蓝点。每一次循环至少有以个蓝点变成白点.

追求吾之所爱