前言

周末(2019/2/23)，Payphone-X学完了唯一的多元最短路，现在，他开始向单元最短路进击啦（给自己一个小小的鼓励）

何为Dijkstra

先看看百度百科对于Dijkstra的解释

迪杰斯特拉算法是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。主要特点是以起始点为中心向外层扩展，直到扩展到终点为止。
——百度百科

……

先不看了……

度娘装高冷的毛病什么时候能改改啊……

还是看看通俗点的解释吧

在前边，我们已经学习了唯一的多元最短路，现在我们学习的Dijkstra是一种单元最短路算法。

（不知道啥是单元最短路的请自觉滚回Floyd）

时间复杂度为 $O(n^2)$ ，比Floyd的暴力三循环快了好多的。

但要注意，Dijkstra只适用于没有负边权的情况。也就是说，如果图中有一条边的边权为负数，就不可以使用Dijkstra了。

Dijkstra的算法实现

在讲算法实现之前，先上一组数据。

5 6    // 5个点，6条边
1 2 4     //1与2之间有一条边权为4的边
2 3 2     //同上
3 5 6
1 4 1
2 4 2
3 4 4
1   //初始点为1

把图建出来大概是这样的

现在我们开始讲Dijkstra的算法实现。

Dijkstra是一种类似于贪心的算法，步骤大概是下边这样：

1.选一个点做起始点。

2.遍历与起始点相连的所有边，寻找出一条最短的记录下来。

3.把这条边的另一个端点作为起始点，然后循环。

下面我们来用数据模拟一下。

首先，我们开一个number数组，用来存储1到点n的估计值。（说估计值是因为当前不一定是最短路，不理解的话一会就知道为什么了）

之后，我们用一个邻接矩阵map存储点i到j的距离，并把map的所有元素初始化为无穷大。

再定义一个start，表示下一个起始点，一个minn，表示下一个起始点到原点的最短距离。

先从1号点开始，得到map[1][2] = 4, map[1][4] = 1，则number[2] = 4, number[4] = 1，3与5两个点没有搜索到，不更新，还是无穷大。

很显然，现在的number数组还不是最终的答案。所以我们要进行第二次更新。

那……

为什么我们要把最短边的另一端点作为下一个起始点呐？

想想看，如果我们把另一端点作为下一次搜索的起始点，就可以得到每一个点到该点的最短路。再加上从这一个端点到初始点的最短路，就可以得到初始点到所有点的最短路啦

之后不断循环，直到循环过所有数据为止 ~~（其实是作者太懒，不想推了）~~

最后答案是0 4 6 1 12

主体代码如下：

void Dijkstra(int s){    //s为初始点编号 
    memset(number , 0x3f, sizeof(number));    //初始化估计值数组 
    int start = s;        //从初始点搜索 
    bj[start] = true;    //标记已被搜索 
    for(int i = 1; i <= n; i ++){
        number[i] = min(number[i] , map[start][i]);//先更新一遍 
    }
    for(int i = 1; i <= n - 1; i ++){
        int minn = 9999999;
        for(int j = 1; j <= n; j ++){
            if(bj[j] == false && number[j] < minn){//找到最近的点，并记录编号，便于下次搜索。 
                minn = number[j];
                start = j;
            }
        }
        bj[start] = true; //注意这句话一定在for循环外，不然会有点搜不到 
        for(int j = 1; j <= n; j ++){
            number[j] = min(number[j] , number[start] + map[start][j]); 
        }   //最后更新一遍 
    }
}

是不是很简单吖（逃）

附件（Dijkstra模板，邻接矩阵实现）

#include<iostream> 
#include<algorithm>

using namespace std;

int number[10001];    //存储估计值 
int map[1001][1001];    //存储邻接矩阵 
int m , n;
int bj[10001];    //用来标记该点是否搜索过 

void Dijkstra(int s){    //s为初始点编号 
    memset(number , 0x3f, sizeof(number));     //初始化估计值数组 
    int start = s;        //从初始点搜索 
    bj[start] = true;    //标记已被搜索 
    for(int i = 1; i <= n; i ++){
        number[i] = min(number[i] , map[start][i]);//先更新一遍 
    }
    for(int i = 1; i <= n - 1; i ++){
        int minn = 9999999;
        for(int j = 1; j <= n; j ++){
            if(bj[j] == false && number[j] < minn){//找到最近的点，并记录编号，便于下次搜索。 
                minn = number[j];
                start = j;
            }
        }
        bj[start] = true; //注意这句话一定在for循环外，不然会有点搜不到 
        for(int j = 1; j <= n; j ++){
            number[j] = min(number[j] , number[start] + map[start][j]); 
        }//最后更新一遍 
    }
}

int main(){
    cin>> n >> m;
    memset(map , 0x3f , sizeof(map));    //初始化邻接矩阵 
    for(int i = 1; i <= m; i ++){
        int a , b , c;
        cin >> a >> b >> c;
        map[a][b] = c;
    }
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            if(i == j){
                 map[i][j] = 0;        //自己到自己的距离为0 
            }               
        }
    }
    int yuan;
    cin >> yuan;
    Dijkstra(yuan);//输入源点。
    for(int i = 1; i <= n; i ++){
        cout << number[i] << " ";
    } 
    return 0;
}
// Written By Payphone-X

【图论算法】Dijkstra

前言

何为Dijkstra

Dijkstra的算法实现

附件（Dijkstra模板，邻接矩阵实现）

THE END