迪杰斯特拉和弗洛伊德算法

一、迪杰斯特拉算法：

1. dijkstra算法概述

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。 ——百度百科

注意该算法要求图中不存在负权边。

2. dijkstra算法原理

这个嘛，迪杰斯特拉百度百科，你可以直接看，如果还不太懂，且听细说：

比如在一个图中，有a, b, c, d, e这5个顶点，用邻接矩阵表示：

改：这个图中，a -> a、b -> b、… e -> e的距离应该为0而非无穷

1. 我的理解，比如初始点为a, （用D(距离)数组记录初始点到所有点的距离）
   初始时，{INF, 3, 3, INF, INF} ——INF表示无穷大
   之后，将进行 （顶点数 - 1）次更新，那么如何更新呢？
   每次找出最小的值，比如在上图中的d（c也可），然后，重点来了
   将起点—到各个点的距离，分别与最小值对应点—到各个点的距离比较

2. 解释一下：为什么要这么做？
   刚开始时，a到b的初始距离最小，那我就琢磨了，能不能通过这个边来更新距离，比如说a到d的距离为无穷大，那么我能不能先选一个最小的权值路径，到达那个顶点，看看从那个顶点能不能来到d，而且使得这两段路径(a => c =>d)的和比 a => d要小，显然是可以的，a -> d 初始为无穷大，然鹅，a可以先到c，a -> c = 3，c -> d = 5，故新的a -> d 的距离：
   D(d)= min(a - > d, a -> c + c -> d) = 8;

3. 初始时的路径权值为无穷大代表的意思是起点和某一点不是直接相连的，所以是“无穷大”， 但是一旦发现可以借助中间点的“搭桥连线”，使得从起点(源点)可以访问到该点后，更新两点距离。不仅是无穷大的距离可以做这样的替换，可能起点和某点两点间存在直接相连的路径，但是由于这条路权值太大，反而不如走到另一点，再从另一点出发到上述的某点的两段权值和小，那么也可更新两点距离，这就是主要思想。

3. 关于路径输出

正如上述所言，一般情况下，初始路径：

如果源点(起点)到各个点的距离不是无穷大，以2. 原理中，邻接矩阵图为例，也就是说，从起点可以直接过去，那么初始时，Path[b]=Path[c]=a;

而为无穷大，说明终点为d、e，在当前状态下是不可能是从源点过来的，所以，Path[d] = Path[e] = -1;

另外，为了方便、统一标准，会把源点Path[a]设为-1，表示源点a前面没有点，这样在路径输出的时候就可以通过判断是否等于-1来停止输出

路径更新：遇到更小权值的路径，需要更新Path，比如初始时Path[e] = -1

但是，有了a=>b=>e这个短路径，那么将Path[e]改为b即可，因为Path[b] = a，所以路径Path[e] => Path[b]即Path[Path[e]] => Path[a]，即为e->b->a

4. 完整代码展示

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 100;

int D[N], S[N];
int Path[N];

typedef struct 
{
    
    int vex[N];
    int arcs[N][N];
    int vexnum, arcnum;

}AMGraph;

void initAndassign(AMGraph &G)
{
    
    cout << "请输入图的顶点和边数：\n";
    cin >> G.vexnum >> G.arcnum;
    for (int i = 0; i < G.vexnum; ++ i) G.vex[i] = i;
    for (int i = 0; i < G.vexnum; ++ i) {
    
        for (int j = 0; j < G.vexnum; ++ j)
            G.arcs[i][j] = INF;
    }
    cout << "请输入两边一权：\n";
    int x, y, w;
    for (int i = 0; i < G.arcnum; ++ i) {
    
        cin >> x >> y >> w;
        G.arcs[x][y] = w;//这是一个有向图
    }
}

void printPath(int v, AMGraph &G)
{
    
    if (v == -1) return;  
    printPath(Path[v], G);
    cout << 'v' << G.vex[v] << "->";
}
        
void dijiestla(AMGraph &G)
{
    
    int st = 0;
    initAndassign(G);
    cout << "请输入起点：" << '\n';
    cin >> st;//起点用st表示(start)
    for (int i = 0; i < G.vexnum; ++ i) {
    
        D[i] = G.arcs[st][i];
        if (D[i] < INF) Path[i] = st;
        else Path[i] = -1;
    }
    D[st] = 0; S[st] = 1; //st为起点，初始时到自身距离为0，并<-->并入集合中
    for (int i = 0; i < G.vexnum; ++ i) {
    
        int v = -1, m = INF;
        for (int k = 0; k < G.vexnum; ++ k) {
    
            if (!S[k] && D[k] < m) {
    
                v = k; m = D[k];
            }
        }
        if (v == -1) continue;
        S[v] = 1;//将v并入集合中
        for (int k = 0; k < G.vexnum; ++ k) {
    
            if (!S[k] && D[v] + G.arcs[v][k] < D[k]) {
    
                D[k] = D[v] + G.arcs[v][k];
                Path[k] = v;
                // cout << "Path["<< k << "] = " << v << '\n';
            }
                
        }
    }
    for (int i = 0; i < G.vexnum; ++ i) {
    
        cout << "最短路径为："; 
        printPath(i, G);
        cout << "最小路径长度为：" << D[i] << '\n';
         
    }
    //for (int i = 1; i <= G.vexnum; ++ i) cout << D[i] << ' ';
    cout << '\n';
}

int main()
{
    
    AMGraph G;
    dijiestla(G);
    system("pause");

    return 0;
}
/*
两组测试材料，对应图1、图2
7 12
0 1 9
0 2 7
0 3 2
2 1 5
2 3 2
3 2 4
1 4 5
3 5 3
5 1 3
5 4 11
4 6 6
5 6 9

6 8
0 2 10
0 4 30
0 5 100
1 2 5
2 3 50
3 5 10
4 3 20
4 5 60
*/

5. 测试图例及结果

图1：

图2：

二、弗洛伊德算法：

1. floyed算法概述

核心：通过一个图的权值矩阵求出它的每两点间的最短路径矩阵

通俗来讲，弗洛伊德算法可以求图中任意两点的最短路径的值以及打印其路径

2. floyed算法原理

与迪杰斯特拉算法一样，都是采用动态规划的思想。算法过程：

1. 从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

2. 对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i] [j] = d，d表示该路的长度；否则G[i] [j] = 无穷大。定义一个矩阵D用来记录所插入点的信息，D[i] [j]表示从Vi到Vj需要经过的点，初始化D[i] [j] = j。把各个顶点插入图中，比较插点后的距离与原来的距离，G[i] [j] = min( G[i] [j], G[i] [k]+G[k] [j] )，如果G[i][j]的值变小，则D[i] [j]=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。 [4]

balabala…其实对floyed算法，想要学好，需要先记住步骤，然后(默写)写代码，最后再在纸面上画一画。你可能会说：“不就是背吗？”，我想说的是：对的，学习第一步是记忆。最后在纸上演示是为了加深理解。

学习是一个由表及里的过程，如果学算法上来就让你弄懂原理，再去写代码，这就违背了这个道理。但是，不能一概而论，容易理解的肯定可以从原理出发，但我想说的是实在不明白的，就需要降低一些要求，先掌握考试、代码，和基本思路、步骤。至于根源，闲时有余力再探！

​ ——以上仅个人观点

3. 关于路径输出问题

关于路径怎么变，看代码就行。

比如，输出v0->v5的路径，那么输出格式为，

Path[v0] [v5] -> Path[v0] [Path[v0] [v5]] ，也就是说，当输出起点和终点进入时，Path第一维不变，始终为起点，第二维在不断更新，当第二维与第一维的数相等，停止输出路径

void printPath(int v1, int v2)
{
    
    int z = Path[v1][v2];
    if (z != v1) printPath(v1, z, G);
    cout << z << "=>" << v2 << ' ';
}

4. 完整代码展示

#include <bits/stdc++.h>

using namespace std;

const int N = 100;
const int INF = 0x3f3f3f3f;

int D[N][N];
int Path[N][N];

typedef struct 
{
    
    int vex[N];
    int arcs[N][N];
    int vexnum, arcnum;

}AMGraph;

void initAndassign(AMGraph &G)
{
    
    cout << "请输入图的顶点和边数：\n";
    cin >> G.vexnum >> G.arcnum;
    for (int i = 0; i < G.vexnum; ++ i) G.vex[i] = i;
    for (int i = 0; i < G.vexnum; ++ i) {
    
        for (int j = 0; j < G.vexnum; ++ j)
            if (i != j) G.arcs[i][j] = INF;
    }
    cout << "请输入两边一权：\n";
    int x, y, w;
    for (int i = 0; i < G.arcnum; ++ i) {
    
        cin >> x >> y >> w;
        G.arcs[x][y] = w;//这是一个有向图
    }
    for (int i = 0; i < G.vexnum; ++ i) {
    
        for (int j = 0; j < G.vexnum; ++ j) {
    
            D[i][j] = G.arcs[i][j];
            if (D[i][j] < INF && i != j) Path[i][j] = i;
            else Path[i][j] = -1;
        }
    }
}

void printPath(int v1, int v2, AMGraph &G)
{
    
    int z = Path[v1][v2];
    if (z != v1) printPath(v1, z, G);
    cout << 'v' << G.vex[z] << "=>" << 'v' << G.vex[v2] << ' ';
}

void floyed(AMGraph &G)
{
    
    initAndassign(G);
    for (int k = 0; k < G.vexnum; ++ k) {
    
        for (int i = 0; i < G.vexnum; ++ i) {
    
            for (int j = 0; j < G.vexnum; ++ j) {
    
                if (D[i][k] + D[k][j] < D[i][j]) {
    
                    D[i][j] = D[i][k] + D[k][j];
                    Path[i][j] = Path[k][j];
                }
            }
        }
    }
    //Path矩阵
    for (int i = 0; i < G.vexnum; ++ i) {
    
        for (int j = 0; j < G.vexnum; ++ j) {
    
            cout << Path[i][j] << ' ';
        }
        cout << '\n';
    }
    cout << '\n';
    
    return;
}

int main()
{
    
    AMGraph G;
    floyed(G);
    cout << "输入起点和终点：" << '\n';
    int v1, v2;
    cin >> v1 >> v2;
    printPath(v1, v2, G);
    cout << '\n';
    
    system("pause");
    return 0;
}
/*
4 8
0 1 1
0 3 4
1 2 9
1 3 2
2 0 3
2 1 5
2 3 8
3 2 6
*/

5. 测试图例与结果

(累死了…www~)

THE END