最短路径--dijkstra
文章目录
- 最短路径的基本概念
- dijsktra的算法思想
- dijkstra的代码实现
- dijkstra的堆优化
- 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的应用场景
该算法适用于边权非负的有向图和无向图,通常用于解决单源最短路径问题。