参考链接：https://www.cnblogs.com/thousfeet/p/9229395.html

1、Floyd

  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.             int temp=e[i][k]+e[k][j];
  5.             if(e[i][j] > temp)
  6.                 e[i][j] = temp;
  7.         }

该算法可得每两顶点之间的最短路情况；

有 n 个顶点；
使用二维数组 e[][] 存储每两个顶点之间边的权值（可为负）；
初始化 e[][] 时，按照需求存入初始值；

由于在任意两个顶点中间经过任意一个顶点都有可能使这两个顶点间的路程变短，所以如代码所示，这种通过中转变短的操作叫做松弛；

2、Dijkstra

  1. for(int i = 1; i <= n; i++)
  2.     dis[i] = e[1][i];
  3. for(int i = 1; i <= n; i++)
  4.     book[i] = 0;
  5. book[1] = 1;
  7. for(int k = 0; k < n-1; k++){
  8.     int min = INF;
  9.     int u;
  10.     for(int i = 1; i <= n; i++)
  11.         if(book[i] == 0 && dis[i] < min){
  12.             min = dis[i];
  13.             u = i;
  14.         }
  15.     book[u] = 1;
  16.     for(int v = 1; v <= n; v++){
  17.         int temp=dis[u] + e[u][v];
  18.         if(e[u][v] < INF && dis[v] > temp)
  19.             dis[v] = temp;
  20.     }
  21. }

为基于贪心策略的求单源最短路的算法；

有 n 个顶点；
e[][] 按需求保存两顶点之间边的权值（不能为负）；
dis[] 保存源点（默认为1号点）到各顶点的距离；
book[] 保存每个点是否用于过松弛的状态；

总体而言，该算法就是每轮从源点开始，选取一个距离源点最近且暂时还没有被用于松弛的点后，使用该点为源点和每个点进行松弛，再将该点打上已用于松弛标记；
需像这样进行 n-1 轮以遍历完全部n个节点，即 book[] 中标记全为1；

3、Bellman-Ford

  1. const int MAXN=100;
  3. struct Exp{
  4.     int x, y;
  5.     int val;
  6. }ex[MAXN];
  8. for(int i = 1; i <= n; i++)
  9.     dis[i] = INF;
  10. dis[1] = 0;
  12. for(int k = 0; k < n-1; k++){
  13.     bool check = 0;
  14.     for(int i = 1; i <= m; i++){
  15.         int temp=dis[ex[i].x] + ex[i].val
  16.         if(dis[ex[i].y] > temp){
  17.             dis[ex[i].y] = temp;
  18.             check = 1;
  19.         }
  20.     }
  21.     if(!check) break;
  22. }
  24. for(int i = 1; i <= m; i++)
  25.     if(dis[ex[i].y] > dis[ex[i].x] + ex[i].val)
  26.         flag = 1;

可进行负权的单源最短路的求解以及正负权回路的判断；

有 n 个顶点， m 个给定边（最多 MAXN 个）；
结构体 Exp 存储每条边开始点 x 、结束点 y 以及权值 val（可为负）；
dis[] 存储每个点到源点（默认为1）的最短距离；
flag 表示该图中，有无正权/负权回路；

dis[] 按照需求进行初始化；
在至多 n-1 轮将 n 个顶点全部遍历的循环中，每轮循环中，设置 check ，如在一次遍历 m 条边的循环中，没有一次满足松弛条件，直接跳出，因为在之后的对k的循环中，将不会再出现松弛动作；
如需判断图中有无正权/负权回路，则可再尝试进行一轮对于全部 m 个给定边的松弛，如果还可进行松弛，则证明存在正权/负权回路；