Dijkstra算法最短路径问题详解

110 阅读 0 评论 73 点赞

我是靠谱客的博主开朗硬币，这篇文章主要介绍Dijkstra算法最短路径问题详解，现在分享给大家，希望可以做个参考。

1、最短路径问题介绍
问题解释：
从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径

2、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的数组的值如下：

代码如下：

复制代码

#include<bits/stdc++.h>
#define Max 1000000
using namespace std;
int n,m;
int G[50][50];
int dist[50];
int visited[50];
void ShortestPath()
{
    int i,j,k,Min;
    for(i = 0;i < n-1;i++)
    {
        Min = Max;
        for(j = 0;j < n;j++)
        {
            if(dist[j] < Min &&visited[j] == 0)
            {
                Min = dist[j];
                k = j;
            }
        }
        visited[k] = 1;
        for(j = 0;j < n;j++)
        {
            if(dist[k] + G[k][j] < dist[j])
                dist[j] = dist[k] + G[k][j];
        }
    }
    for(i = 0;i < n;i++)
    {
        if(i != m)
        {
            if(dist[i] == Max)
                cout<<-1<<' ';
            else
                cout<<dist[i]<<' ';
        }
    }
}
int main()
{
   cin>>n>>m;
   int i,j,c;
   for(i = 0;i < n;i++)
   {
       if(i != m)
        visited[i] = 0;
       else
        visited[i] = 1;
   }
   for(i = 0;i < n;i++)
    for(j = 0;j < n;j++)
   {
       cin>>c;
       if(c == 0 && i != j)
        G[i][j] = Max;
       else
        G[i][j] = c;
   }
    for(i = 0;i < n;i++)
    {
         dist[i] = G[m][i];
    }
   ShortestPath();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
#define Max 1000000
using namespace std;
int n,m;
int G[50][50];
int dist[50];
int visited[50];
void ShortestPath()
{
    int i,j,k,Min;
    for(i = 0;i < n-1;i++)
    {
        Min = Max;
        for(j = 0;j < n;j++)
        {
            if(dist[j] < Min &&visited[j] == 0)
            {
                Min = dist[j];
                k = j;
            }
        }
        visited[k] = 1;
        for(j = 0;j < n;j++)
        {
            if(dist[k] + G[k][j] < dist[j])
                dist[j] = dist[k] + G[k][j];
        }
    }
    for(i = 0;i < n;i++)
    {
        if(i != m)
        {
            if(dist[i] == Max)
                cout<<-1<<' ';
            else
                cout<<dist[i]<<' ';
        }
    }
}
int main()
{
   cin>>n>>m;
   int i,j,c;
   for(i = 0;i < n;i++)
   {
       if(i != m)
        visited[i] = 0;
       else
        visited[i] = 1;
   }
   for(i = 0;i < n;i++)
    for(j = 0;j < n;j++)
   {
       cin>>c;
       if(c == 0 && i != j)
        G[i][j] = Max;
       else
        G[i][j] = c;
   }
    for(i = 0;i < n;i++)
    {
         dist[i] = G[m][i];
    }
   ShortestPath();
    return 0;
}