Dijkstra及其堆优化

基本介绍

Dijkstra算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

实现方式

Dijkstra采用了一种贪心的方法，每次找离起点最近的一个点，并且用这个点来更新与他相邻的点的到起点的距离。

用$dis[i]$来表示与起点的距离。

因为每次需要找到离起点最近的点，也就是$dis[i]$最小的点，需要用一个循环，会浪费一定的时间。

所以我们可以使用优先队列来进行优化，也就是Dijkstra的堆优化。

Dijkstra详解。

1、Dijkstra模板

#include <iostream>
using namespace std;

const int MAX = 110,INF=1e9;
int Map[MAX][MAX],dis[MAX],mark[MAX];
int	n,m;

int dijkstra(int s,int f){
	for(int i = 1;i <= f;i++){
		mark[i]=0;
		dis[i]=Map[s][i];
	}
	mark[s]=1;
	dis[s]=0;
	int node;
	for(int i = 1;i <= n;i++){
		int min =INF;
		for(int i = 1;i <= n;i++){
			if(!mark[i]&&dis[i]<min){
				min=dis[i];
				node=i;
			}
		}
		mark[node]=1;
		for(int i = 1;i <= n;i++){
			int tmp=min+Map[node][i];
			tmp=tmp>INF?INF:tmp;
			if(!mark[i]&&dis[i]>tmp)	dis[i]=tmp;
		}
	}
	return dis[f];
}

void init(){
	for(int i = 0;i <= MAX;i++){
		for(int j = 0;j <= MAX;j++){
			Map[i][j]=INF;
		}
		Map[i][i]=0;
	}
}

int main(){
	while(~scanf("%d %d",&n,&m)){
		if(!n||!m)	break;
		init();
		int l,r,dis;
		for(int i = 0;i < m;i++){
			scanf("%d %d %d",&l,&r,&dis);
			if(Map[l][r]>dis||Map[r][l]>dis)
				Map[l][r]=Map[r][l]=dis; 
		}
		int ans=dijkstra(1,n);
		printf("%d\n",ans);
	}
}

2、Dijkstra堆优化

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 1e3 + 5, INF = 1e9;
int head[N], cnt, vis[N], dis[N], n;
struct {
	int to, val, next;
}Map[N];
struct node {
	int u, c;
	node(int a = 0, int b = 0) :u(a), c(b) { }
	bool operator <(const node& a) const {
		return c > a.c;//小顶堆
	}
};

void Dijkstra(int s) {
	memset(vis, 0, sizeof(vis));
	for (int i = 1; i <= n; i++)	dis[i] = INF;
	dis[s] = 0;
	priority_queue<node>q;
	q.push(node(s, 0));
	node t;
	while (!q.empty()) {
		t = q.top();
		q.pop();
		int u = t.u;
		if (vis[u])	continue;
		vis[u] = 1;
		for (int i = head[u]; ~i; i = Map[i].next) {
			int x = Map[i].to;
			int c = Map[i].val;
			if (!vis[x] && dis[x] > dis[u] + c) {
				dis[x] = dis[u] + c, q.push(node(x, dis[x]));
			}
		}
	}
}

void build(int u, int v, int val) {
	Map[++cnt].to = v, Map[cnt].val = val;
	Map[cnt].next = head[u], head[u] = cnt;
}

int main() {
	int m;
	cin >> n >> m;
	cnt = 0;
	memset(head, -1, sizeof(head));
	for (int i = 1; i <= m; i++) {
		int u, v, val;
		cin >> u >> v >> val;
		build(u, v, val);
	}
	Dijkstra(1);
	cout << dis[n] << endl;
}