最近看了《算法笔记》上面关于最短路径的部分，学习了一种之前没见过的算法：SPFA。
理论上SPFA算法会比Dijkstra快，顾而找了一题测试一下。
使用PAT A1072题，因为这题求最短路径的部分很单纯，没有其他的权，而且测试点的复杂度够高，能够看出时间上的差别。
题目链接

速度对比（重点看测试点4）

Dijkstra速度

image.png

SPFA

image.png
多次提交对比，Dijkstra算法都在50ms左右，而SPFA一直在10ms左右，可见SPFA确实比Dijkstra快不少，而且思路也不复杂，以后可以多多使用。

代码如下

  1. #include<bits/stdc++.h>
  2. #include<unordered_map>
  3. using namespace std;
  4. #define MAXNODE 1015
  5. #define INF 0x3ffffff
  6. #define G2index(G) ((n)+(G))
  7. #define index2G(index) ((index)-(G))
  9. struct Node
  10. {
  11.     int v, dis;//目标与距离
  12. };
  14. int dis[MAXNODE];
  15. int n, m, k, dmax;
  16. bool used[MAXNODE], inqueue[MAXNODE];
  17. vector<Node> graph[MAXNODE];
  19. void Dijkstra(int start)
  20. {
  21.     fill(dis, dis + MAXNODE, INF);
  22.     fill(used, used + MAXNODE, false);
  23.     dis[start] = 0;
  25.     for (int i = 0; i < n + m - 1; i++) {
  26.         int minnode = -1, mindis = INF;
  27.         for (int j = 1; j <= n + m; j++) {
  28.             if (!used[j] && dis[j] < mindis) {
  29.                 minnode = j;
  30.                 mindis = dis[j];
  31.             }
  32.         }
  33.         if (minnode == -1)
  34.             return;
  36.         used[minnode] = true;
  37.         int tdis = dis[minnode];
  38.         for (Node node : graph[minnode]) {
  39.             if (tdis + node.dis < dis[node.v]) {
  40.                 dis[node.v] = tdis + node.dis;
  41.             }
  42.         }
  43.     }
  44. }
  46. void SPFA(int start)
  47. {
  48.     fill(dis, dis + MAXNODE, INF);
  49.     fill(inqueue, inqueue + MAXNODE, false);
  50.     dis[start] = 0;
  52.     int tdis = 0;
  53.     queue<int> q;
  54.     for (Node node : graph[start]) {
  55.         if (tdis + node.dis < dis[node.v]) {
  56.             dis[node.v] = node.dis + tdis;
  57.             q.push(node.v);
  58.             inqueue[node.v] = true;
  59.         }
  60.     }
  61.     while (!q.empty()) {
  62.         int nodeid = q.front();
  63.         q.pop();
  64.         inqueue[nodeid] = false;
  65.         for (Node node : graph[nodeid]) {
  66.             tdis = dis[nodeid];
  67.             if (tdis + node.dis < dis[node.v]) {
  68.                 dis[node.v] = node.dis + tdis;
  69.                 if (!inqueue[node.v]) {
  70.                     q.push(node.v);
  71.                     inqueue[node.v] = true;
  72.                 }
  73.             }
  74.         }
  75.     }
  76. }
  78. struct Ans
  79. {
  80.     int Gid, mindis, totaldis;
  81. };
  82. vector<Ans> ans;
  84. void getans(int Gid)
  85. {
  86.     int totaldis, mindis;
  87.     mindis = INF;
  88.     totaldis = 0;
  89.     for (int i = 1; i <= n; i++) {
  90.         if (dis[i] > dmax)
  91.             return;
  92.         if (dis[i] < mindis) {
  93.             mindis = dis[i];
  94.         }
  95.         totaldis += dis[i];
  96.     }
  97.     ans.push_back(Ans{ Gid,mindis,totaldis });
  98. }
  100. int main() {
  101.     scanf("%d%d%d%d", &n, &m, &k, &dmax);
  102.     for (int i = 0; i < k; i++) {
  103.         int c1, c2, dd;
  104.         char cs1[10], cs2[10];
  105.         scanf("%s%s%d", cs1, cs2, &dd);
  106.         if (cs1[0] == 'G') {
  107.             c1 = G2index(atoi(cs1 + 1));
  108.         }
  109.         else {
  110.             c1 = atoi(cs1);
  111.         }
  113.         if (cs2[0] == 'G') {
  114.             c2 = G2index(atoi(cs2 + 1));
  115.         }
  116.         else {
  117.             c2 = atoi(cs2);
  118.         }
  119.         graph[c1].push_back(Node{ c2, dd });
  120.         graph[c2].push_back(Node{ c1, dd });
  121.     }
  122.     for (int i = 1; i <= m; i++) {
  123.         //Dijkstra(G2index(i));
  124.         SPFA(G2index(i));
  125.         getans(i);
  126.     }
  128.     Ans myans;
  129.     myans.Gid = -1;
  130.     myans.totaldis = INF;
  131.     myans.mindis = 0;
  132.     for (Ans a : ans) {
  133.         if (a.mindis > myans.mindis)
  134.             myans = a;
  135.         else if (a.mindis == myans.mindis) {
  136.             if (a.totaldis < myans.totaldis)
  137.                 myans = a;
  138.         }
  139.     }
  140.     if (myans.Gid == -1) {
  141.         printf("No Solution");
  142.         return 0;
  143.     }
  144.     printf("G%d\n%.1lf %.1lf", myans.Gid, (double)myans.mindis, (double)myans.totaldis / n);
  145.     return 0;
  146. }

代码思路就不写了，大家可以看算法笔记。