当前位置:   article > 正文

最短路径:地图软件是如何计算出最优出行路径的?—— 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)。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/446822
推荐阅读
相关标签
  

闽ICP备14008679号