桂林论坛网app_建站行业严重产能过剩_查询网站流量_武汉百度信息流广告

最短路径的基本概念

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的应用场景

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