最短路径--dijkstra

最短路径的基本概念

1.路径长度：一条路径上所经过的边的数目
2.带权路径长度：路径上所经过边的权值之和
3.最短路径：带权路径长度值最小的那条路径
那么在一个图中，我们如果要求出起点到终点的最短路径，我们就需要用到最短路径算法。常见的最短路径算法有dijkstra，Floyd ，Ford，SPFA四种，我们这节仅介绍dijkstra算法。

dijsktra的算法思想

dijkstra算法的实质其实时不断更新dist数组的值（一个松弛的过程）来遍历图，最终得出起点到每一个点的最短路径长度。该算法基于贪心思想，初始时将起点到自己的距离设置为0，其它点都设置为无穷大，找到未被标记的dist数组中的最小值时，将其标记为1，再对该点的邻接点进行松弛操作重复即可。

dijkstra的代码实现

这里以邻接矩阵存储。

#include<iostream>
#define INF 10005
using namespace std;
int n, m;
int dist[105];//点i到起点的距离
int g[105][105];
int ans;
int vis[105];
int path[105];
void dijktra(int start) {
    vis[start] = 1;
	dist[start] = 0;
	path[start] = start;
	for (int i = 1;i <= n;i++) {
		if (g[start][i] < dist[i] && vis[i] == 0) {
           dist[i] = g[start][i];
		   path[i] = start;
		}
	}
	int t, minn;
	for (int j = 2;j <= n;j++) {
		minn = INF;
		t = -1;
		for (int i = 1;i <= n;i++) {
			if (minn > dist[i]&&vis[i]==0) {
				minn = dist[i];
				t = i;
			}
		}
		vis[t] = 1;
		for (int i = 1;i <= n;i++) {
			if (g[t][i]+dist[t] < dist[i] && vis[i] == 0) {
				dist[i] = g[t][i] + dist[t];
				path[i] = t;
			}
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= n;j++) {
			if (i != j) {
                g[i][j] = INF;
			}	
		}
	}
	int x, y, w;
	while (m--) {
		cin >> x >> y >> w;

		g[x][y] = g[y][x] = w;
	}
	cin >> x;
	dijktra(x);
	for (int i = 1;i <= n;i++) {
		printf("起点到%d的最短距离是%d,该路径为%d", i, dist[i],i);
		 int p = i;
		 while (path[p] != p) {
			 printf("%d ", p);
			 p = path[p];
		 }
		 printf("%d\n", p);

	}
	
	return 0;
}

dijkstra的堆优化

这里用到了c++ stl里面的优先队列的小顶堆，以链式前先星存储。

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
int n, m,cnt;
int dis[105];
int vis[105];
int s;
int head[105];
priority_queue<PII, vector<PII>, greater<PII>>q;
struct edge {
	int to, next, w;
}e[10005];
void add(int x, int y, int w) {
	e[cnt].to = y;
	e[cnt].w = w;
	e[cnt].next = head[x];
	head[x] = cnt;
	cnt++;
}
void dijkstra() {
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	q.push({ 0,s });
	while (!q.empty()) {
		PII t = q.top();
		q.pop();
		int u = t.second,d=t.first;
		if (vis[u])continue;
		vis[u] = 1;
		for (int i = head[u]; i != -1; i = e[i].next) {
			int v = e[i].to;
			if (vis[v] == 0 && dis[v] > dis[u] + e[i].w) {
				dis[v] = dis[u] + e[i].w;
				q.push({ dis[v],v });
			}
		}
	}
}
int main() {
	cin >> n >> m>>s;
	int x, y, w;
	memset(head, -1, sizeof(head));
	for (int i = 1; i <= m; i++) {
		cin >> x >> y >> w;
		add(x, y, w);
	}
	dijkstra();
	for (int i = 1; i <= n; i++) {
		cout << dis[i] << " ";
	}
	return 0;
}

dijkstra的应用场景

该算法适用于边权非负的有向图和无向图，通常用于解决单源最短路径问题。