迪杰斯特拉算法

【概念】

Dijkstra算法是求解从一个顶点到其余各顶点的最短路径的算法，解决的是有向无环图中最短路径问题。

【原理】 

　　1.首先，引入一个辅助向量D，它的每个分量 D 表示当前所找到的从起始点 （即源点 ）到其它每个顶点的长度。例如，D[3] = 2表示从起始点到顶点3的路径相对最小长度为2。这里强调相对就是说在算法执行过程中D的值是在不断逼近最终结果但在过程中不一定就等于长度。

　　2.D的初始状态为：若从V到Vi有弧（即从V到Vi存在连接边）,则D[i]为弧上的权值（即为从 到 的边的权值）；否则置D[i]为∞。显然，长度为 D = Min{ D | Vi∈V } 的路径就是从V出发到顶点Vi的长度最短的一条路径。

　　3.那么，下一条长度次短的是哪一条呢？也就是找到从源点V到下一个顶点的最短路径长度所对应的顶点，且这条最短路径长度仅次于从源点V到顶点Vi的最短路径长度。假设该次短路径的终点是，则可想而知，这条路径要么是( ) ，或者是( )。它的长度或者是从V到Vk的弧上的权值，或者是D[i]加上从Vj到Vk的弧上的权值。

　　4.一般情况下，假设S为已求得的从源点  出发的最短路径长度的顶点的集合，则可证明：下一条次最短路径（设其终点为  ）要么是弧(  )，或者是从源点 出发的中间只经过S中的顶点而最后到达顶点  的路径。因此，下一条长度次短的的最短路径长度必是D  = Min{ D  |  ∈V-S }，其中D  要么是弧(  )上的权值，或者是D  (  ∈S)和弧(  ,  )上的权值之和。

算法描述如下：

　　1）令arcs表示弧上的权值。若弧不存在，则置arcs为∞（在本程序中为MAXCOST）。S为已找到的从  出发的的终点的集合，初始状态为空集。那么，从  出发到图上其余各顶点  可能达到的长度的初值为D=arcs[Locate Vex(G,  )]，  ∈V；

　　2）选择

  

，使得D

  

=Min{ D |

  

∈V-S } ；

　　3）修改从

  

出发的到集合V-S中任一顶点

  

的最短路径长度。

　　Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合T，初始时，源点 s 的路径权重被赋为 0 （dis[s] = 0），若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为W（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。 然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点， 然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。 然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。

【Dijkstra算法示例演示】

下面我求下图，从顶点v1到其他各个顶点的最短路径

 

首先第一步，我们先声明一个dis数组，该数组初始化的值为：

我们的顶点集T的初始化为：T={v1}

　　既然是求 v1顶点到其余各个顶点的最短路程，那就先找一个离 1 号顶点最近的顶点。通过数组 dis 可知当前离v1顶点最近是 v3顶点。当选择了 2 号顶点后，dis[2]（下标从0开始）的值就已经从“估计值”变为了“确定值”，即 v1顶点到 v3顶点的最短路程就是当前 dis[2]值。将V3加入到T中。 为什么呢？因为目前离 v1顶点最近的是 v3顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得 v1顶点到 v3顶点的路程进一步缩短了。因为 v1顶点到其它顶点的路程肯定没有 v1到 v3顶点短.

　　OK，既然确定了一个顶点的最短路径，下面我们就要根据这个新入的顶点V3会有出度，发现以v3 为弧尾的有： < v3,v4 >,那么我们看看路径：v1–v3–v4的长度是否比v1–v4短，其实这个已经是很明显的了，因为dis[3]代表的就是v1–v4的长度为无穷大，而v1–v3–v4的长度为：10+50=60，所以更新dis[3]的值,得到如下结果：

因此 dis[3]要更新为 60。这个过程有个专业术语叫做“松弛”。即 v1顶点到 v4顶点的路程即 dis[3]，通过 < v3,v4> 这条边松弛成功。这便是 Dijkstra 算法的主要思想：通过“边”来松弛v1顶点到其余各个顶点的路程。

　　然后，我们又从除dis[2]和dis[0]外的其他值中寻找最小值，发现dis[4]的值最小，通过之前是解释的原理，可以知道v1到v5的最短距离就是dis[4]的值，然后，我们把v5加入到集合T中，然后，考虑v5的出度是否会影响我们的数组dis的值，v5有两条出度：< v5,v4>和 < v5,v6>,然后我们发现：v1–v5–v4的长度为：50，而dis[3]的值为60，所以我们要更新dis[3]的值.另外，v1-v5-v6的长度为：90，而dis[5]为100，所以我们需要更新dis[5]的值。更新后的dis数组如下图：

　　然后，继续从dis中选择未确定的顶点的值中选择一个最小的值，发现dis[3]的值是最小的，所以把v4加入到集合T中，此时集合T={v1,v3,v5,v4},然后，考虑v4的出度是否会影响我们的数组dis的值，v4有一条出度：< v4,v6>,然后我们发现：v1–v5–v4–v6的长度为：60，而dis[5]的值为90，所以我们要更新dis[5]的值，更新后的dis数组如下图：

　　然后，我们使用同样原理，分别确定了v6和v2的最短路径，最后dis的数组的值如下：

因此，从图中，我们可以发现v1-v2的值为：∞，代表没有路径从v1到达v2。所以我们得到的最后的结果为：

起点 终点 最短路径 长度
v1 v2 无 ∞ 
v3 {v1,v3} 10
v4 {v1,v5,v4} 50
v5 {v1,v5} 30
v6 {v1，v5,v4,v6} 60

【程序实现】

#include<iostream>
#include<climits>
#include<string>
using namespace std;

/*
本程序是使用Dijkstra算法实现求解最短路径的问题
采用的邻接矩阵来存储图
*/

//记录起点到每个顶点的最短路径的信息
class Dis {
public:
    string path;
    int value;
    bool visit;
    Dis() {
        visit = false;
        value = 0;
        path = "";
    }
};

class Graph_DG {
private:
    int vexnum;     //图的顶点个数
    int edge;      //图的边数
    int **arc;    //邻接矩阵
    Dis * dis;   //记录各个顶点最短路径的信息
public:

    Graph_DG(int vexnum, int edge);
    ~Graph_DG();
    
    bool check_edge_value(int start, int end, int weight);  // 判断我们每次输入的的边的信息是否合法,顶点从1开始编号
   
    void createGraph();      //创建图
    
    void print();   //打印邻接矩阵
    
    void Dijkstra(int begin);   //求最短路径
    
    void print_path(int);   //打印最短路径
};

//构造函数
Graph_DG::Graph_DG(int vexnum, int edge) {
    //初始化顶点数和边数
    this->vexnum = vexnum;
    this->edge = edge;
    //为邻接矩阵开辟空间和赋初值
    arc = new int*[this->vexnum];
    dis = new Dis[this->vexnum];
    for (int i = 0; i < this->vexnum; i++) {
        arc[i] = new int[this->vexnum];
        for (int k = 0; k < this->vexnum; k++) {
                arc[i][k] = INT_MAX;    //邻接矩阵初始化为无穷大
        }
    }
}

//析构函数
Graph_DG::~Graph_DG() {
    delete[] dis;
    for (int i = 0; i < this->vexnum; i++) {
        delete this->arc[i];
    }
    delete arc;
}

// 判断我们每次输入的的边的信息是否合法顶点从1开始编号
bool Graph_DG::check_edge_value(int start, int end, int weight) {
    if (start<1 || end<1 || start>vexnum || end>vexnum || weight < 0) {
        return false;
    }
    return true;
}

void Graph_DG::createGraph() {
    cout << "请输入每条边的起点和终点（顶点编号从1开始）以及其权重" << endl;
    int start;
    int end;
    int weight;
    int count = 0;
    while (count != this->edge) {
        cin >> start >> end >> weight;
        //首先判断边的信息是否合法
        while (!this->check_edge_value(start, end, weight)) {
            cout << "输入的边的信息不合法，请重新输入" << endl;
            cin >> start >> end >> weight;
        }
        //对邻接矩阵对应上的点赋值
        arc[start - 1][end - 1] = weight;
        ++count;
    }
}

void Graph_DG::print() {
    cout << "图的邻接矩阵为：" << endl;
    int count_row = 0; //打印行的标签
    int count_col = 0; //打印列的标签
    //开始打印
    while (count_row != this->vexnum) {
        count_col = 0;
        while (count_col != this->vexnum) {
            if (arc[count_row][count_col] == INT_MAX)
                cout << "∞" << " ";
            else
            cout << arc[count_row][count_col] << " ";
            ++count_col;
        }
        cout << endl;
        ++count_row;
    }
}

void Graph_DG::Dijkstra(int begin){
    //首先初始化我们的dis数组
    int i;
    for (i = 0; i < this->vexnum; i++) {
        //设置当前的路径
        dis[i].path = "v" + to_string(begin) + "-->v" + to_string(i + 1);
        dis[i].value = arc[begin - 1][i];
    }
    //设置起点的到起点的路径为0
    dis[begin - 1].value = 0;
    dis[begin - 1].visit = true;

    int count = 1;
    //计算剩余的顶点的最短路径（剩余this->vexnum-1个顶点）
    while (count != this->vexnum) {
        //index用于保存当前dis数组中最小的那个下标
        //min记录的当前的最小值
        int index=0;
        int min = INT_MAX;
        for (i = 0; i < this->vexnum; i++) {
            if (!dis[i].visit && dis[i].value<min) {
                min = dis[i].value;
                index = i;
            }
        }
        
        //把index对应的顶点加入到已经找到的最短路径的集合中
        dis[index].visit = true;
        ++count;
        for (i = 0; i < this->vexnum; i++) {
            //注意这里的条件arc[index][i]!=INT_MAX必须加，不然会出现溢出，从而造成程序异常
            if (!dis[i].visit && arc[index][i]!=INT_MAX && (dis[index].value + arc[index][i]) < dis[i].value) {
                //如果新得到的边可以影响其他为访问的顶点，那就就更新它的最短路径和长度
                dis[i].value = dis[index].value + arc[index][i];
                dis[i].path = dis[index].path + "-->v" + to_string(i + 1);
            }
        }
    }

}

void Graph_DG::print_path(int begin) {
    string str = "v" + to_string(begin);
    cout << "以"<<str<<"为起点的图的最短路径为：" << endl;
    for (int i = 0; i != this->vexnum; i++) {
        if(dis[i].value!=INT_MAX)
            cout << dis[i].path << "=" << dis[i].value << endl;
        else {
            cout << dis[i].path << "是无最短路径的" << endl;
        }
    }
}

bool check(int Vexnum, int edge) {
    if (Vexnum <= 0 || edge <= 0 || ((Vexnum*(Vexnum - 1)) / 2) < edge)
        return false;
    return true;
}

int main() {

    int vexnum; int edge;

    cout << "输入图的顶点个数和边的条数：" << endl;
    cin >> vexnum >> edge;

    while (!check(vexnum, edge)) {
        cout << "输入的数值不合法，请重新输入" << endl;
        cin >> vexnum >> edge;
    }

    Graph_DG graph(vexnum, edge);
    graph.createGraph();
    graph.print();
    graph.Dijkstra(1);
    graph.print_path(1);
    return 0;
}