1.Floyd

        Floyd算法核心是遍历每一个节点，然后看这个点K是否是其他两个点A,B的中间点，如果是，且经过K会比原先两点距离近，则更新这两点间的距离为Dis(A,B) = Dis(A,K) + Dis(K,B) :

        AB之间的距离为5，当遍历到C点，因为C点是AB点的中间点，且AC（2）+BC（2）C也是BD的中间点，单是BC（2）+ DC（6）>BD（3），因此BD距离不变

        C还是AD的中间点，AD的距离从无限大变为 AC(2)+CD(6) = 8

        同理，当把B选为K的时候，由于DB（3）+CB（2）< CD（6）, 可以把CD的距离更新为5

        B也是AD的中间点，AD的距离就是AB(4)+BD(3)=7

        此外，当选择A/D为K的时候，并没有可以缩短的距离，最终获得是即所有点的最近距离，比如AB是4，AC是2，CD是5，AD是7

代码如下，根据代码可以看出Floyd算法复杂度为O(n^3)

#include <iostream>
#include <array>
using namespace std;

array<array<int, 4>, 4> arr;

void line(int n, int m, int val){
    arr[n][m] = val;
    arr[m][n] = val;
}

int main() {
    for (size_t i = 0; i < arr.size(); i++)
        arr[i].fill(100);
    
    line(0,1,5);
    line(0,2,2);
    line(1,2,2);
    line(1,3,3);
    line(2,3,6);

    for (size_t k = 0; k < arr.size(); k++)
        for (size_t i = 0; i < arr.size(); i++)
            for (size_t j = 0; j < arr.size(); j++)
                if (arr[i][j] > arr[i][k]+arr[k][j])
                    arr[i][j] = arr[i][k]+arr[k][j];

    for (size_t i = 0; i < arr.size(); i++)
        for (size_t j = 0; j < arr.size(); j++)
            if (i != j && arr[i][j] != 100)
                cout << static_cast<char>(i+'A') << "->" << static_cast<char>(j+'A') << "=" << arr[i][j] << endl;
            
    return 0;
}
//输出
A->B=4
A->C=2
A->D=7
B->A=4
B->C=2
B->D=3
C->A=2
C->B=2
C->D=5
D->A=7
D->B=3
D->C=5

2.Dijkstra

        Dijkstra算法是典型的贪心+搜索算法，每次都是取最小值作为下一个点，然后再从下一个点继续搜索下个点。比如求下图A到F的最短路径，具体的步骤如下：

        首先定义一个数组，从A到其他点的距离，从上图可以知道：A到A的距离是0，A到B是1，A到C是2，A与其他点不相连，因此是无穷大

        接着，把A标记一下，说明A这个点已经计算过其相邻节点。然后找出数组中没有标记过的最小节点B，同理更新数组中与B相邻的节点的距离，节点D/F是B的下个节点，因此更新D的值为1+3=4，F的值为1+7=8，并把标记B为已处理

        继续做同样的事，选择数组中最小的C点，对其邻居进行访问，C的下个节点只有D，由于D目前是4，小于2+3=5，因此D的值不变，C标记为已访问

        继续选择处理D，变更E为4+2=6，标记D，处理E，此时E的下一个节点为F，且距离为6+1=7，比原先的8要小，因此更新F的值为8，标记E

        最后处理F，因为F没有未处理的相邻的节点，因此结束算法，得到A到其他点的最短路径。

        注意Dijkstra算法不支持计算含有权为负数的图的路径，因为如果有负值边，如下图，当计算C的时候，把D更细昵成-1，此时会发现A到B其实有更短的值0，但是B已经计算过了，这就矛盾了，因此不能有负数的边

        代码如下

#include <iostream>
#include <array>
using namespace std;

array<array<int, 6>, 6> arr;
array<int, 6> dis;
array<int, 6> flag;

void line(int n, int m, int val){
    arr[n][m] = val;
    arr[m][n] = val;
}

int GetMinPos() {
    //找出最小点
    int val = 100;
    int pos = 0;
    for (size_t p = 0; p < 6; p++)
    {
        if (flag[p] == 0 && dis[p] < val)
        {
            val = dis[p];
            pos = p;
        }
    }
    return pos;
}

int main() {
    for (size_t i = 0; i < arr.size(); i++)
        arr[i].fill(100);
    
    for (size_t i = 0; i < arr.size(); i++)
        arr[i][i] = 0;
    
    line(0,1,1);
    line(0,2,2);
    line(1,3,3);
    line(1,5,7);
    line(2,3,3);
    line(3,4,2);
    line(4,5,1);

    //创建一个距离数组
    for (size_t i = 0; i < 6; i++)
        dis[i] = arr[0][i];

    //记录是否处理过
    flag.fill(0);
    flag[0] = 1;
    
    //循环5次
    for (size_t i = 1; i < 6; i++)  
    {
        int pos = GetMinPos();
        flag[pos] = 1;
        for (size_t j = 0; j < 6; j++) //j = i+1;
        {
            if (flag[j] == 0 && dis[pos] + arr[pos][j] < dis[j])
                dis[j] = dis[pos] + arr[pos][j];
        }
    }
    
    //输出各点到A的最小距离
    for (size_t i = 0; i < 6; i++)
        cout << dis[i] << " ";
    cout << endl;
    
    return 0;
}
//输出结果
0 1 2 4 6 7 

3.Bellman-Ford

        还是上面的图，Ford算法流程如下，先定义一个距离数组，表示各点到A的距离。

        然后遍历每个点，先从A开始，遍历A开始的边 AB=1, AC=2，因为目前AB，AC等于无穷，因此更新B,C的距离为1，2，更新后如下图：

        继续取下一个点B，遍历B开始的边BD=3,BF=7,  则可以更新D值为4（1+3），F的值为8（1+7），更新后如下图：

        继续处理点C，没有更新数组的任何点，再处理点D, 因为 DE=2， 把E更新为6（4+2）

        继续处理点E，EF=1, 因为AE(6)+EF(1)<8, 因此把F更新成7，最后处理F, 没有从F点开始的边，因此结束，最终结果：

        代码如下：注意Ford算法可以处理负数边，但是不能处理带负数带回路的情况

#include <iostream>
#include <cstring>
using namespace std;

int arr[6][6] = {};
int dis[6] = {};

int main(){
    memset(arr, 100, sizeof(int)*36);
    arr[0][1] = 1;
    arr[0][2] = 2;
    arr[1][3] = 3;
    arr[2][3] = 3;
    arr[1][5] = 7;
    arr[3][4] = 2;
    arr[4][5] = 1;
    memset(dis, 100, sizeof(int)*6);
    dis[0] = 0;

    for (int i = 0; i < 6; i++) //遍历点
    {
        for (int j = 0; j < 7; j++) //遍历边
        {
            if (dis[i] + arr[i][j] < dis[j])
                dis[j] = dis[i] + arr[i][j];
        }
    }
    
    for (size_t i = 0; i < 6; i++)
        cout << dis[i] << " ";
    cout << endl;
}
//最终结果
0 1 2 4 6 7 

4.SPFA

        SPFA算法是Bellman-Ford算法的优化，用队列存放待处理的节点，这与广度搜索的方式基本一样，先把第一个节点放进去，然后取出来，遍历边，目的点距离有改变的且不在队列中，则把目的节点放入待处理队列中，直到把队列中的节点处理完毕。

        代码如下：这里使用set替代了队列，最终效果是一样的

#include <iostream>
#include <cstring>
#include <set>
using namespace std;

int arr[6][6] = {};
int dis[6] = {};
set<int> procset;

int main(){
    memset(arr, 100, sizeof(int)*36);
    arr[0][1] = 1;
    arr[0][2] = 2;
    arr[1][3] = 3;
    arr[2][3] = 3;
    arr[1][5] = 7;
    arr[3][4] = 2;
    arr[4][5] = 1;
    memset(dis, 100, sizeof(int)*6);
    dis[0] = 0;
    procset.emplace(0);

    do
    {
        //取出一个待处理的
        auto it = procset.begin();
        int i = *it;
        procset.erase(it);
        for (int j = 0; j < 7; j++) //遍历边
        {
            if (dis[i] + arr[i][j] < dis[j])
            {
                dis[j] = dis[i] + arr[i][j];
                procset.emplace(j); //有变化就待处理
            }
        }
    } while (!procset.empty());
    
    for (size_t i = 0; i < 6; i++)
        cout << dis[i] << " ";
    cout << endl;
}
//最终输出
0 1 2 4 6 7