最短路Dijkstra算法讲解

还是以举例子为主吧，部分图片来自于网络。

在下边的学习中，主要是通过松弛操作让最短路的值进行替换。dijie斯特拉指定一个点（源点）到其余的各个顶点的最短路径，也叫做“单源最短路径”。

例如下图中的1号顶点到2，3，4，5，6顶点的最短路径：

在这里要和flody算法一样，在这儿也需要用二维数组e来存取顶点之间和边之间的关系，数值如下：

在这儿我们还需要用一个一维数组dis来存取1号顶点到各个顶点的初始路程，如下：

因为dis中存取的是各个顶点到1号顶点的初始距离，所以我们把dis数组中的值称为最短路的“估计值”。

既然我们是求1号顶点到其余各个顶点的最短路程，那我们就可以先找一个距离1号顶点比较近的顶点。

我们通过看dis数组可知距离1号最近的是2号顶点。当我们选择了2号顶点之后，dis[2] 中的值由一个“估计值”变成了一个“确定值”，即1号顶点到2号顶点的最短路程就变成了当前的dis[2]的值。

当我们选定了2号顶点，我们接下来看2号顶点有哪些出边，有2–>3和2–>4这两条边，我们可以通过讨论2–>3这条边是否让1号到3号顶点的路程，也就是说现在我们来比较dis[3] 和 dis[2] + e[2][3] 的大小，其中dis[3] 表示1号顶点到3号顶点的路程：dis[2]
+e[2][3]中dis[2]表示1号顶点到2号顶点的路程， e[2][3]表示2–>3这条边。所以dis[2] + dis[2][3] 就表示从1号顶点到2号顶点，再通过2–>3这条边，到达3号顶点的路程。

dis[3] = 12 , dis[2] + e[2][3] = 1 + 9 = 10   ，dis[3] > dis[2] + e[2][3] ,因此dis[3] 要更新为10，这个过程我们成为“松弛”，1号顶点到3号顶点的路程即dis[3] , 通过2–>3这条边松弛成功。

这就是dijkstra的主要思想：通过“边”来松弛1号顶点到其余各个顶点的路程。

   同理，我们可以通过2–>4(e[2][4]),我们可以将dis[4]的值从∞ 松弛为4（dis[4]初始为∞，dis[2] + e[2][4] = 1 + 3 = 4 , dis[4] > dis[2] + e[2][4] , 因此dis[4]的更新为4）

   我们对2号顶点松弛之后的dis数组为：

我们对4号顶点的所有边(4 — > 3 , 4 –> 5 和 4–>6)还用刚才的方法进行松弛，松弛之后为：

接下来对3号顶点的所有出边（3–>5)进行松弛，松弛之后的dis数组为：

对5号顶点的所有出边(5 –> 4）进行松弛，松弛完毕的dis数组为：

最后对6号顶点的所有出边进行松弛，得到最终的dis数组，这就是1号到所有点的最短路径：

         我们来对上边的算法来进行一个总结，上述的算法的思想是：每次找到离源点（上述例子的源点就是1号顶点）最近的一个点，然后以该顶点为中心进行扩展，最终得到源点到其他点的最短路径。

完整的dijkstra的算法代码如下：

#include<iostream>
#include<cstdio>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1009;
int e[MAXN][MAXN];
 
int main()
{
    int dis[MAXN] , book[MAXN] ;
    int n , m , t1 , t2 , t3 , u , v , mi;
    while(cin >> n >> m)   //n??????,m??????
    {
        for(int i = 1 ; i <= n ; i ++)   //???
        {
            for(int j = 1 ; j<= n ; j ++)
            {
                if(i == j)
                    e[i][j] = 0;
                else
                    e[i][j] = INF;
            }
        }
 
        for(int i = 1 ; i <= m ; i ++)
        {
            cin >> t1 >> t2 >> t3;
            e[t1][t2] = t3;
        }
 
        for(int i = 1 ; i <= n ; i ++) //???dis??,???1?????????????
        {
            dis[i] = e[1][i];
        }
 
        //book ??????
        for(int i = 1 ; i <= n ; i ++)
            book[i] = 0;
        book[1] = 0;
 
        //dijkstra???????
        for(int i = 1 ; i <= n ; i ++)
        {
            //????1???????
            mi = INF;
            for(int j = 1 ; j <= n ; j ++)
            {
                if(book[j] == 0 && dis[j] < mi)
                {
                    mi = dis[j];
                    u = j;
                }
            }
            book[u] = 1;
            for(int v = 1 ; v <= n ; v ++)
            {
                if(e[u][v] < INF)
                {
                    if(dis[v] > dis[u] + e[u][v])
                        dis[v] = dis[u] + e[u][v];
                }
            }
        }
        //???????
        for(int i = 1 ; i <= n ; i ++)
        {
            cout<<dis[i]<<" ";
        }
    }
    return 0 ;
}
/*
6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
0 1 8 4 13 17
*/