优先级队列+邻接矩阵+Dijkstra算法

发表于 | Edited on | 分类于 | 次阅读

优先级队列+邻接矩阵+Dijkstra算法

DijkStra算法代码

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
// 定义Edge表示每一条边，from是始点，to是汇点，distance表示距离
struct Edge {
	int from, to, distance;
	Edge(int f, int t, int d) :from(f), to(t), distance(d) {};
	bool operator <(const Edge& e)const { return this->distance > e.distance; };
};

// graph 表示图，以邻接矩阵形式表示，其中0编号顶点不算在图中。
// source表示源点
// distance表示从source到其他顶点的距离数组
// visit[i]表示顶点i是否在源点所在的集合中
void dijkstra(const vector<vector<int>>& graph, const int source, vector<int>& distance) {
	vector<int> visit(graph.size(), 0);
	priority_queue<Edge> myQueue;
	visit[0] = 1;
	visit[source] = 1;
	// 初始时往优先级队列中加入从源点发出的所有的边
	for (int i = 1; i < graph.size(); ++i)
		if(visit[i]==0)
			myQueue.emplace(source, i, distance[i]);
	
	while (!myQueue.empty()) {
		Edge e = myQueue.top();
		myQueue.pop();
		if (visit[e.to] == 1)
			continue;
		visit[e.to] = 1;
		distance[e.to] = e.distance;
		for (int j = 1; j < graph.size(); ++j) {
			if (visit[j] == 0 && distance[e.to] + graph[e.to][j] < distance[j]){
				myQueue.emplace(e.to, j, distance[e.to] + graph[e.to][j]);
			}
		}
	}
}

复杂度分析

最多每条边都进入优先级队列，每次进入后队列调整用时logm，所以复杂度为O(mlogn)