Dijkstra Algorithm

Dijkstra算法 求解最短路径问题(边权非负)

用于求解一个结点到其余各节点的最短路径
运用广度优先搜索思想

算法思想

假设出发顶点为v，顶点集合为V{v1,v2,…}，v到V中各顶点距离构成的集合为D{…}

• 从D集合中找到di最小的一个移除集合(除它本身)，并且移出V中所对应的顶点vi
• D中元素进行更新，di=min(di,从v出发经过上次步骤所得到的一系列vi到达D中未被访问过顶点的距离)
• 重复执行上述步骤，直到找到所有的目标顶点

上述操作对应具体实现(朴素版本)

const int maxNum = 100;const int INF = 1e9;int dist[maxNum], pre[maxNum], len[maxNum][maxNum];int n, m;//点  边bool vis[maxNum];void Dijkstra(int begin) {memset(dist, 0, sizeof(dist));memset(pre, 0, sizeof(pre));memset(vis, false, sizeof(vis));for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {len[i][j] = INF;}}for (int i = 1; i <= n; i++) {dist[i] = len[begin][i];if (dist[i] == INF)pre[i] = 0;else pre[i] = begin;}dist[begin] = 0;vis[begin] = true;for (int i = 0; i < n - 1; i++) {int tmp = INF;int vertex = begin;for (int j = 1; j <= n; j++) {if (!vis[j] && dist[j] < tmp) {vertex = j;tmp = dist[j];}}vis[vertex] = true;for (int j = 1; j <= n; j++) {if (!vis[j] && len[vertex][j]) {int newDis = dist[vertex] + len[vertex][j];if (newDis < dist[j]) {dist[j] = newDis;pre[j] = vertex;}}}}}

模板题

题目描述
给定一个 n 个点，m 条有向边的带非负权图，请你计算从 s 出发，到每个点的距离。

数据保证你能从 ss 出发到任意点。

输入格式
第一行为三个正整数 n, m, s。 第二行起 m 行，每行三个非负整数 u_i, v_i, w_i ，表示从 u_i到 v_i有一条权值为 w_i的有向边。

输出格式
输出一行 n 个空格分隔的非负整数，表示 s 到每个点的距离。

输入输出样例

4 6 11 2 22 3 22 4 11 3 53 4 31 4 4

0 2 4 3

优化版本(priority_queue)

#include<bits/stdc++.h>using namespace std;const int LEN = 1e5 + 5;const int INF = 0x3f3f3f3f;int n, m, s;struct Edge {int begin, end, dis;int preIndex, next;/*bool operator<(const Edge& e)const {return this->dis > e.dis;}*/}edge[LEN*2];int head[LEN], dis[LEN];bool vis[LEN];priority_queue<pair<int, int> >q;void Dijkstra() {q.push(make_pair(0, s));while (!q.empty()) {int front = q.top().second;q.pop();if (vis[front])continue;vis[front] = true;for (int i = head[front]; i; i = edge[i].next) {int end = edge[i].end;int tmp = dis[front] + edge[i].dis;if (tmp < dis[end]) {dis[end] = tmp;q.push(make_pair(-dis[end], end));//为了取小}}}}int main() {ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m >> s;fill(dis + 1, dis + 1 + n, INF);dis[s] = 0;for (int i = 1; i <= m; i++) {int u, v, w;cin >> u >> v >> w;edge[i].begin = u;edge[i].end = v;edge[i].dis = w;edge[i].next = head[u];head[u] = i;}Dijkstra();for (int i = 1; i <= n; i++) {cout << dis[i] << \" \";}cout << endl;return 0;}