Dijkstra算法简介

Dijkstra算法计算是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到起点距离最近且未访问过的顶点的邻接节点，直到扩展到所有终点为止。

数据结构抽象

现在我们有一个景点地图，假设从1号顶点出发，求到其他各个顶点的最短路径。算法步骤如下：
设置地图的带权邻接矩阵为map[][]，如果从顶点 i 到顶点 j 有边，则map[i][j] == <i,j>的权值，否则map[i][j] == (无穷大)。

邻接矩阵为map[ ][ ]抽象为一个二维数组，表示每两个顶点之间的权值，[ i ][ j ]和[ j ][ i ]表示两个顶点之间不同方向的权值。

初始化

令集合S={ 1 }，S初始化只包含起点u，集合V-S = { 2，3，4，5 }，对于集合V-S中的所有顶点x，初始化最短距离数组dist[ i ] = map[ 1 ] [ i ]，dist[ u ]=0（起点到起点为0）如图3所示。如果源点1到顶点 i 有边相连，初始化前驱数组p[ i ] = 1，否则p[ i ] = -1，如图4所示。
最短距离数组dist[ i ] ，表示顶点1到其他顶点之间的最短距离，该数组经过每次计算会动态变化。

前驱数组p[ i ]，表示到达该顶点的前一个顶点编号，也是动态变化的。

开始计算

第一轮计算

1.找最小
在集合V-S = {2，3，4，5} 中，依照贪心策略来寻找 V-S集合中dist[ ]最小的顶点 T，如图3，找到最小值为2，对应的顶点 T = 2。
2. 加入S集合
将顶点T = 2加入集合S中，S={1， 2}，同时更新V-S = {3，4，5}，如图5所示。

3. 走捷径
刚刚找到了起点到 T = 2的最短路径，那么对集合 V-S中所有 T 的邻接点，都可以借助 T 走捷径。我们从图或邻接矩阵都可以看出，2号顶点的邻接点是3和4号顶点，如图2所示。

先看3号结点能否借助2号走捷径: dist[2] + map[2][3] = 2+2 = 4，而当前dist[3] = 5>4，因此可以走捷径即2–3，更新dist[3] = 4，记录顶点3的前驱为2，即p[3] = 2。

再看4号结点能否借助2号走捷径:如果dist[2] + map[2][4] = 2+6 = 8，而当前dist[4] = ∞ > 8.因此可以走捷径即2-4，更新dist[4] = 8，记录顶点4的前驱为2，即p[4] = 2。
更新后如图6和图7所示。

第二轮计算

1.找最小
在集合 V-S = {3，4，5)中，依照贪心策略来寻找dist[]中具有最小值的顶点T，找到最小值为4，对应的结点T = 3，如图6。
2. 加入S集合
将顶点T = 3加入集合S中，S={1，2，3}，同时更新V-S = {4，5}，如图8所示。

3. 走捷径
刚刚找到了源点到T = 3 的最短路径，那么对集合 V-S中所有T的邻接点 ，都可以借助T走捷径。我们从图或邻接矩阵可以看出，3号结点的邻接点是4和5号结点

先看4号结点能否借助3号走捷径:dist[3]+map[3][4] = 4+7 = 11，而当前dist[4] = 8 < 11，比当前路径还长，因此不更新。

再看5号结点能否借助3号走捷径:dist[3]+map3][5] = 4+1 = 5，而当前dis[5] = ∞ > 5，因此可以走捷径，即3一5，更新dist[5] = 5，记录顶点5的前驱为3，即p[5] = 3，更新后如图9和图10 所示。

第三轮计算

1.找最小
在集合 V-S = {4，5}中，依照贪心策略来寻找V- S 集合中dist[ ] 最小的顶点T，如图9所示，找到最小值为5，对应的结点T = 5。
2. 加入S集合
将顶点T = 5加入集合S中，S = {1，2，3，5}，同时更新V-S = {4}，如图11所示。

3. 走捷径
刚刚找到了源点到T = 5的最短路径，那么对集合V-S中所有T = 5的邻接点，都可以借助T = 5走捷径。我们从图或邻接矩阵可以看出，5 号结点没有邻接点，因此不更新，如图9 和图10 所示。

第四轮计算

1.找最小
在集合 V-S = {4}中，依照贪心策略来寻找 dist最小的顶点，只有一个顶点，所以很容易找到，找到最小值为8，对应的结点T= 4，如图9所示。
2. 加入S集合
将顶点T=4加入集合S中，S = {1，2，3，5，4}，同时更新 V-S = { }，如图12所示。

3. 走捷径
V-S = { }为空，算法停止。

算法总结

map[i][j]：把图抽象为二维数组，下标代表各个顶点，值代表两个顶点ij之间的权值。
S集合：已经遍历且找到最短路径的顶点集合。
V-S集合：还未遍历的顶点集合，最短路径在寻找中。
T：当前正在遍历的顶点。
dist[ i ] ： 最短距离数组，表示当前起点到其他顶点之间的最短距离，该数组经过每次计算会动态变化。
p[ i ]：前驱数组，表示当前到达该顶点的前一个顶点编号，也是动态变化的。

算法的关键是理解走捷径：
走捷径的意思是：已找到起点到T的最短路径，起点到T的最短路径 + T到T的邻接顶点P的权值 < 当前记录起点到P的最短路径，则更新P的最短路径和前一跳。

每轮计算都是重复的操作，直到遍历了图中所有顶点，得到dist[ ]和p[ ]。
可求得从源点图中其余各个顶点的最短路径及长度，也可通过前驱数组逆向找到最短路径上经过的顶点。
例如，p[5] = 3，即5的前驱是3，p[3] = 2，即3的前驱是2，p[2] = 1，即2的前驱是1，p[1] = -1，1没有前驱，那么从起点1到5的最短路径为1-2-3-5。

C++实现Dijkstra算法

头文件

#ifndef DIJKSTRA_H
#define DIJKSTRA_H

#include <string>
#include <fstream>
#include <iostream>
#include <vector>
#define MAX_VERNUM 20//最大顶点数
#define MAX_VALUE 99999//最大权值
using namespace std;

//顶点
struct Node
{
    string path;           //路径
    string NodeName;       //节点名字
    vector<string> next_Node;//从起点开始到终点所经过的节点，不包括起点
    int value;             //路径权值
    bool visit;            //是否访问过
    Node()
    {
        visit = false;
        value = 0;
        NodeName = "";
        next_Node.clear();
        path = "";
    }
};

class Dijkstra
{
public:
    Dijkstra();
    ~Dijkstra();

    void Create_graph();                    //创建图
    void Dijkstra_cpt(string from);         //迪斯拉算法求最短路径
    void Display_table(string from);        //输出路由表

    void Modify_edge(string from, string to, int value);                        //修改边
    void Add_node(string nodename);                      //添加顶点
    void Del_node(string r1);                      //删除顶点
private:
    int vernum;                             //图的顶点个数
    int **adjmatrix;                        //邻接矩阵
    Node *node;                             //记录各个顶点最短路径的信息
};

#endif // DIJKSTRA_H

源文件

#include "Dijkstra.h"

int g_nodeNum = 5;//顶点数量
int g_edgeNum = 8;//边的数量
int g_edge[8][3] = {//边的集合
    //起点，终点，权值
    {1, 2, 2},
    {1, 3, 5},
    {2, 3, 2},
    {2, 4, 6},
    {3, 4, 7},
    {3, 5, 1},
    {4, 3, 2},
    {4, 5, 4}
};

Dijkstra::Dijkstra()
{

}

//析构函数
Dijkstra::~Dijkstra()
{
    delete[] node;                      //释放一维数组node内存
    for (int i = 0; i < MAX_VERNUM; i++)//释放二维数组adjmatrix内存
    {
        delete this->adjmatrix[i];
    }
    delete adjmatrix;
}

//创建图
void Dijkstra::Create_graph()
{
    vernum = g_nodeNum;                    //初始化顶点数和边数
    node   = new Node[MAX_VERNUM];              //保留顶点信息，其中共有MAX_VERNUM条边
    adjmatrix = new int*[MAX_VERNUM];         //数组一维长度为MAX_VERNUM
    for (int i = 0; i < MAX_VERNUM; i++)
    {
        adjmatrix[i] = new int[MAX_VERNUM];   //数组二维长度也为MAX_VERNUM
        for (int k = 0; k < MAX_VERNUM; k++)
        {
            adjmatrix[i][k] = MAX_VALUE;      //邻接矩阵初始化为无穷大
        }
    }

    for(int index=0;index<g_edgeNum;index++)
    {
        //对邻接矩阵对应上的点赋值
        adjmatrix[g_edge[index][0] - 1][g_edge[index][1] - 1] = g_edge[index][2];
    }

    for (int i = 0; i < this->vernum; i++)    //初始化node数组的编号
    {
        node[i].NodeName = "r" + to_string(i + 1);
    }
}

//算法主体
void Dijkstra::Dijkstra_cpt(string from)
{
    int f, i, j, k;
    for (f = 0; f < this->vernum; f++)
    {
        if (from.compare(node[f].NodeName) == 0)
            break;
    }
    for (i = 0; i < this->vernum; i++)//初始化node数组
    {
        node[i].path = from + "-->" + node[i].NodeName;
        node[i].next_Node.clear();
        node[i].next_Node.push_back(node[i].NodeName);
        node[i].value = adjmatrix[f][i];
        node[i].visit = false;
    }
    node[f].value = 0;                //设置起点到起点的路径为0
    node[f].visit = true;

    for (i = 1; i < this->vernum; i++)//计算剩余的顶点的最短路径
    {
        int temp = 0;                 //temp用于保存当前node数组中最小的那个下标
        int min = MAX_VALUE;          //min记录的当前的最小值
        for (j = 0; j < this->vernum; j++)
        {
            if (!node[j].visit && node[j].value < min)
            {
                min = node[j].value;
                temp = j;
            }
        }
        node[temp].visit = true;      //把temp对应的顶点加入到已经找到的最短路径的集合中
        for (k = 0; k < this->vernum; k++)
        {
            //起点到T的最短路径 + T到T的邻接顶点P的权值  < 当前记录起点到P的最短路径
            if (!node[k].visit && adjmatrix[temp][k] != MAX_VALUE && (node[temp].value + adjmatrix[temp][k]) < node[k].value)
            {
                node[k].path = node[temp].path + "-->" + node[k].NodeName;
                node[k].next_Node = node[temp].next_Node;
                node[k].next_Node.push_back(node[k].NodeName);
                node[k].value = node[temp].value + adjmatrix[temp][k];
            }
        }
    }
    Display_table(from);
}

//输出路由表
void Dijkstra::Display_table(string from)
{
    int i;
    bool flag = false;
    for (i = 0; i < this->vernum; i++)
    {
        if (from.compare(node[i].NodeName) == 0)
           flag = true;
    }
    if (flag == false)
        printf("can not found node\n");
    else
    {
        printf("start:%s\n",from.c_str());
        for (i = 0; i < this->vernum; i++)
        {
            cout << "dest:" << node[i].NodeName << "  ";
            printf("next:%s,value:%d\n",node[i].next_Node.at(0).c_str(),node[i].value);
        }
    }
    cout << endl;
}

//添加边
void Dijkstra::Modify_edge(string from,string to,int value)
{
    int f, t;
    for (f = 0; f < this->vernum; f++)    //找到起点对应的数组坐标
    {
        if (from.compare(node[f].NodeName) == 0)
            break;
    }
    for (t = 0; t < this->vernum; t++)    //找到终点对应的数组坐标
    {
        if (to.compare(node[t].NodeName) == 0)
            break;
    }
    adjmatrix[f][t] = value;              //对邻接矩阵对应上的点赋值
}

//添加顶点
void Dijkstra::Add_node(string nodename)
{
    node[vernum].NodeName = nodename;
    this->vernum++;
}

//删除顶点
void Dijkstra::Del_node(string r1)
{
    int r2, i, j, count = 0;
    for (r2 = 0; r2 < this->vernum; r2++)
    {
        if (r1.compare(node[r2].NodeName) == 0)
            break;
    }
    for (i = 0; i < this->vernum; i++)  //统计与删除的顶点相关的边数
    {
        if(adjmatrix[r2][i] != MAX_VALUE)
            count++;
    }

    for(i = 0;i < this->vernum; i++)    //调整邻接矩阵
    {
        for(j = 0;j < this->vernum; j++)//将邻接矩阵向内紧缩
        {
            if(i > r2 && j > r2)        //调整右下角部分
                adjmatrix[i-1][j-1] = adjmatrix[i][j];
            else if(i > r2)             //调整右上角部分
                adjmatrix[i-1][j] = adjmatrix[i][j];
            else if(j > r2)             //调整左下角部分
                adjmatrix[i][j-1] = adjmatrix[i][j];
        }
    }
    for(i = 0;i < this->vernum; i++)
    {
        adjmatrix[this->vernum][i] = MAX_VALUE;
        adjmatrix[i][this->vernum] = MAX_VALUE;
    }

    for(i = r2; i < this->vernum-1; i++)//调整顶点数组值
        node[i] = node[i+1];
    this->vernum--;
}

调用

    mDijkstra.Create_graph();
    mDijkstra.Dijkstra_cpt("r1");

打印：

start:r1
dest:r1  next:r1,value:0
dest:r2  next:r2,value:2
dest:r3  next:r2,value:4
dest:r4  next:r2,value:8
dest:r5  next:r2,value:5