Dijkstra算法

90 阅读 0 评论 60 点赞

我是靠谱客的博主神勇冬瓜，这篇文章主要介绍Dijkstra算法，现在分享给大家，希望可以做个参考。

搜索与图论

dijkstra算法
基本思路
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中包含了图的所有顶点。
在这里插入图片描述如图计算从v1出发到v7最短路径,首先设置距离数组dist[N],dist[i],表示vi距离起点的路径，最开始都默认无穷大。然后从起点开始遍历，起点为v1，dist[1]更新为0，与v1直接相连的节点都直接更新

然后选择其中最短路径的节点，并以此更新相关节点路径。根据上表，选择v4，dist[4]=60，并更新与v4相关节点。如dist[6]<dist[4]+g[4][6],所以dist[6]=60+50=110，选择过的节点将不会继续选择，以下是更新后的距离表。
在这里插入图片描述
继续按照原来的方法寻找距离起点最短的节点，以此节点作为更新的媒介，下图为以v2为中间点更新后的距离表
然后依次类推，直到所有节点被遍历完，最后可以得出每个节点到起点的最短路径。

1.朴素版：
时间复杂是 O(n²+m), n 表示点数，m 表示边数，适合稠密图
关键代码

复制代码

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
#include <iostream>
#include <cstring> 
using namespace std;
const int N=510;
int g[N][N];
int dist[N];//表示从1到某个点的距离
int n,m;
bool st[N];//表示某个点的最短距离是否确定
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            {
            
			    if (!st[j] && (t == -1 || dist[t] > dist[j]))
                {
                    t = j;
				} 
            }
        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            {
			   dist[j] = min(dist[j], dist[t] + g[t][j]);
			}
        st[t] = true;
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}


int main(int argc, char** argv) {
	memset(g,0x3f,sizeof g);
	cin>>n>>m;
	while(m--)
	{
		int i,j,t;
		cin>>i>>j>>t;
		g[i][j]=min(g[i][j],t);
	}
	int k=dijkstra();
	cout<<k;
	return 0;
}

2.堆优化版
时间复杂度 O(mlogn), n 表示点数，m 表示边数
为了最快寻找到最小距离的点，利用堆结构降低时间复杂度
建立小根堆，每次取得堆顶元素进行比较和更新数据

复制代码

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
typedef pair<int, int> PII;
const int IF=0x3f3f3f3f
int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // first存储距离，second存储节点编号

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if (dist[n] == IF) return -1;
    return dist[n];