最短路径：地图软件是如何计算出最优出行路径的？—— Dijkstra 算法 。_导航软件计算最短路径的算法分析

一、算法解析：

我们可以把地图抽象成一个有权有向图，每一个路口都是一个图的顶点，每一条两路口之间的路的距离就是边的权重。路的行驶方向就是边的方向。

那么我们求最优出行路径就可以转化成在一个有向有权图中，求两个顶点之间的最短路径。

二、举例如下

假设我们有下图这样的有权有向图，我们要从起点0到终点5找到最优（短）路径

三、算法解析，Dijkstra 算法 ，准备如下：

1、我们代码建立如下图的邻接表

2、其次我们需要一个小顶堆，用来保存所有的当前访问的顶点。如下图

3，我们还需要一个数组用于记录我们的路径。如下图

四、算法（代码）过程详解

1、首先我们建立了如上图的邻接表。

2、我们将起点加入小顶堆，然后弹出dist最小的点，此时就是起点自己。

3、遍历弹出的点（此时是0,0）的以它为起点的边（用到邻接表），将这些边的终点计算出dist，然后放进小顶堆中。（如果已经访问过了，就不用加进小顶堆，只要刷新就行。）

4、再次从小顶堆中去除dist最小的点，然后遍历它的边。

5、重复上面的步骤，直至小顶堆中取出的是终点。

代码循环过程图解

五、代码

#include<iostream>
#include<vector>
#include<deque>
using namespace std;

/*
Dijkstra算法，求最短路径
使用有向有权图
路口为顶点，路段为有向有权边
*/

//有向有权图邻接表表示

class Graph
{

private:
	struct vertex
	{
		int id;
		int dist;
	};
	struct Edge
	{
		int sid;//起点
		int tid;//终点
		int w;//边权重
		Edge(int s, int t, int w) :sid(s), tid(t), w(w) {}
	};
	int _v;//顶点数
	vector<vector<Edge*>*> _adj;//保存顶点之间的关系
	int* _predececossor;//申请内存用于保存路径
	vertex* _vertexs;//保存起始点到当前点的（最短）路径。会不断刷新
	bool* _inqueue;//表示是否进过队列
	deque<vertex> minHeap;//使用双端队列模拟最小堆，头部永远是最小的那个

public:
	Graph(int v) :_v(v)
	{
		_predececossor = new int[v];
		_vertexs = new vertex[v];
		_inqueue = new bool[v];
		for (int i = 0; i < v; ++i)
		{
			_adj.push_back(new vector<Edge*>);
		}
	}
	//添加边，并根据边关系填充_adj顶点数据邻接表,s表示起点，t表示终点，w表示边权重
	void addEdge(int s, int t, int w)
	{
		_adj[s]->push_back(new Edge(s, t, w));
	}

	void Dijkstra(int s, int t)//用于寻找最短路径的起点s和终点t
	{
		for (int i = 0; i < _v; ++i)
		{
			_vertexs[i].id = i;
			_vertexs[i].dist = INT_MAX;//初始化的时候dist距离未知先设置为最大值,dist是起始点到该点的最短距离
		}
		_vertexs[s].id = s;
		_vertexs[s].dist = 0;//因为s是起始点，所以dist距离为0；

		minHeap.push_front(_vertexs[s]);//因为是空的双端队列，所以直接插入头部
		_inqueue[_vertexs[s].id] = true;
		while (!minHeap.empty())
		{
			int index = 0;
			vertex minVertex;
			for (int i = 0; i < minHeap.size(); ++i)
			{
				if (minHeap[i].dist < minHeap[index].dist)
				{
					index = i;
				}
			}
			minVertex = minHeap[index];
			minHeap[index] = minHeap[0];
			minHeap.pop_front();//弹出头部元素，因为已经被取出到vertex
			if (minVertex.id == t)break;//抵达终点
			for (int i = 0; i < _adj[minVertex.id]->size(); ++i)
			{
				Edge e = *(_adj[minVertex.id]->at(i));//遍历以minVertex为起点的边(都存在_adj中)
				vertex nextVertex = _vertexs[e.tid];
				if (minVertex.dist + e.w < nextVertex.dist)
				{
					nextVertex.dist = minVertex.dist + e.w;
					_vertexs[e.tid].dist = nextVertex.dist;
					_predececossor[nextVertex.id] = minVertex.id;
					if (_inqueue[nextVertex.id] == true)
					{
						for (auto& itr : minHeap)
						{
							if (itr.id == nextVertex.id)
							{
								itr.dist = nextVertex.dist;
							}
						}
					}
					else
					{
						minHeap.push_back(nextVertex);
						_inqueue[nextVertex.id] = true;
					}
				}
			}
		}
	}
	void print(int s, int t)//起点s终点t
	{
		int nowId = t;
		cout << t << endl;
		while (nowId != s)
		{
			cout << _predececossor[nowId] << endl;
			nowId = _predececossor[nowId];
		}
	}
};

int main()
{
	Graph g(6);
	g.addEdge(0, 1, 10);
	g.addEdge(0, 4, 15);
	g.addEdge(1, 2, 15);
	g.addEdge(1, 3, 2);
	g.addEdge(4, 5, 10);
	g.addEdge(2, 5, 5);
	g.addEdge(3, 2, 1);
	g.addEdge(3, 5, 12);
	g.Dijkstra(0, 5);
	g.print(0, 5);

	system("pause");
	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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

六、总结：

Dijkstra 算法的时间复杂度是多少？
在刚刚的代码实现中，最复杂就是 while 循环嵌套 for 循环那部分代码了。while 循环最多会执行 V 次（V 表示顶点的个数），而内部的 for 循环的执行次数不确定，跟每个顶点的相邻边的个数有关，我们分别记作 E0，E1，E2，……，E(V-1)。如果我们把这 V 个顶点的边都加起来，最大也不会超过图中所有边的个数 E（E 表示边的个数）。
for 循环内部的代码涉及从优先级队列取数据、往优先级队列中添加数据、更新优先级队列中的数据，这样三个主要的操作。
我们知道，优先级队列是用堆来实现的，堆中的这几个操作，时间复杂度都是 O(logV)（堆中的元素个数不会超过顶点的个数 V）。所以，综合这两部分，再利用乘法原则，整个代码的时间复杂度就是 O(E*logV)。