最短路径(Dijkstra算法)

---

Dijkstra算法刚接触时确实有点难以理解，尤其是代码的实现，但其背后的逻辑实际上是用贪心算法来支撑的。但是在算法学习中Dijkstra算法又是最基本的一种算法，对于求解单源最短路径有着极大的作用。在这里我简单讲一下自己的理解，我的代码参考了《图解数据结构》，该代码适合稠密图，使用的是邻接矩阵来存储的图。

---

1、Dijkstra算法主要步骤

对于贪心算法，简单描述一下：
贪心算法正如其名字一样，贪心算法只注重眼前利益，就像贪心的小人一样，因此得名贪心算法，该算法即从一个初始解，一步步选取当前最优解，最终得出近似的最优解（注意：不一定是该问题的最优解，而是近似于最优解）。
实现该算法的基本过程如下。
（1）从问题的某一初始解出发。
（2）while能向给定总目标前进一步。
（3）求出可行解的一个解元素。
（4）由所有解元素组合成问题的一个可行解。
（想更深入了解请参考链接https://blog.csdn.net/effective_coder/article/details/8736718?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164621206116781685343755%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=164621206116781685343755&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-8736718.pc_search_result_control_group&utm_term=%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E8%AF%A6%E8%A7%A3&spm=1018.2226.3001.4187）

---

2、Dijkstra算法小结

1、Dijkstra算法一般是用来解决单源最短路径问题（指定一个点（源点）到其余各个顶点的最短路径，也叫做“单源最短路径”。）
2、其时间复杂度仅为O(n^2^)，并且非常高效，甚至可以优化成O(log2n)。
3、Dijkstra算法中权值只能为正数，若权值为负数则不能使用该算法。（权值即图各个边所赋予的值）

---

3、算法实现

#include <iostream>
#include <iomanip>
 
using namespace std;
 
#define SIZE 7
#define NUMBER 6
#define INFINITE 123456  //宏定义无穷大
 
//首先定义图的数组
int Graph_Matrix[SIZE][SIZE];
int Distance[SIZE];  //路径长度
 
//建立有向图
void Create_Graph(int *Path_Cost)
{
    int i,j;
    for(i=0;i<SIZE;i++)
    {
        for(j=0;j<SIZE;j++)
        {
            //若是在对角线上，设置元素值为0
            if(i==j)
            {
                Graph_Matrix[i][j]=0;
            }
            //其他位置元素的值为无穷大
            else
            {
                Graph_Matrix[i][j]=INFINITE;
            }
        }
    }
 
    int End_Point,Start_Point;  //图的边起始位置和终止位置
 
    //存入图的各个数据：边，权重
    i=0;
    while(i<SIZE)
    {
        Start_Point=Path_Cost[i*3];  //在邻接矩阵中的行
        End_Point=Path_Cost[i*3+1];  //在邻接矩阵中的列
        //图各边权值转化为邻接矩阵中所在的位置
        Graph_Matrix[Start_Point][End_Point]=Path_Cost[i*3+2];
        i++;
    }
}
 
//打印邻接矩阵
void Print_Matrix()
{
    int i=0,j=0;
    for(i=1;i<SIZE;i++)
    {
        cout << "vex" << i ;
        for(j=1;j<SIZE;j++)
        {
            //为了美观和可读性，将值为无穷大的元素打印为x
            if(Graph_Matrix[i][j]==INFINITE)
            {
                cout << setw(5) << "x";
            }
            else
            {
                cout << setw(5) << Graph_Matrix[i][j];
            }
        }
        cout << endl;
    }
}
 
//开始求解单源最短路径
void Shortest_Path(int vertex1,int vertex_total)
{
    int Shortest_vertex=1;  //初始化
    int Shortest_distance;  //最短距离
    int flag[SIZE];  //标志数组，标志顶点是否已经遍历过
    int i,j;
 
    for(i=1;i<=vertex_total;i++)
    {
        flag[i]=0;  //初始化标志数组
        Distance[i]=Graph_Matrix[vertex1][i];  //将图的权值存入Distance[]数组中
    }
 
    flag[vertex1]=1;  //标志该顶点已经找过
    Distance[vertex1]=0;  //顶点到该顶点自身的距离为0
 
    for(i=0;i<=vertex_total-1;i++)
    {
        Shortest_distance=INFINITE;
        for(j=0;j<=vertex_total;j++)
        {
            //找到最小权边的顶点
            if(flag[j]==0 && Distance[j]<=Shortest_distance)
            {
                Shortest_distance=Distance[j];
                Shortest_vertex=j;
            }
        }
 
        flag[Shortest_vertex]=1;  //找到下一个顶点后标记为已经经过
 
        for(j=0;j<=vertex_total;j++)
        {
            //以上一个顶点为父节点，若前一个顶点和下一个权边的和最小，则更新最短路径
            if(flag[j]==0 &&
               Distance[Shortest_vertex]+Graph_Matrix[Shortest_vertex][j]
               <Distance[j])
            {
                //更新最短路径
                Distance[j]=Distance[Shortest_vertex]+Graph_Matrix[Shortest_vertex][j];
            }
        }
    }
}
 
int main()
{
    int Path_Cost[9][3]={{1,2,3},{1,3,5},{1,4,1},{1,5,3},{1,6,4},
                         {2,5,3},{4,5,7},{4,6,6},{4,3,2}};
    cout << "========================================="  << endl;
    cout << "此范例图的邻接矩阵如下：" << endl;
    cout << "=========================================" << endl;
    cout << "顶点   vex1 vex2 vex3 vex4 vex5 vex6" << endl;
    Create_Graph(&Path_Cost[0][0]);
    Print_Matrix();
    cout << "========================================="  << endl;
    cout << "顶点1到各顶点最短距离的最终结果" << endl;
    cout << "========================================="  << endl;
    //查找最短路径
    Shortest_Path(1,NUMBER);
    for(int i=1;i<SIZE;i++)
    {
        cout << "顶点1" << "到顶点" << i << "的最短距离=" << Distance[i] << endl;
    }
 
    system("pause");
    return 0;
}