基于邻接矩阵的朴素Dijkstra单源最短路C++极简实现

本文主要是介绍基于邻接矩阵的朴素Dijkstra单源最短路C++极简实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

基于邻接矩阵的Dijkstra实现

最近刷题遇到了1个最短路算法的题: https://leetcode-cn.com/problems/network-delay-time/，我就在想有没有一个最佳的通用的朴素Dijkstra的C++实现。看了一些解答，有一个很经典，核心逻辑20行左右，没有任何冗余操作，像是搞ACMer同学的风格。核心实现如下：

#include <vector>
#include <algorithm>
#include <cstdio>using namespace std;/*** @param graph, 图的邻接矩阵表示* @param start, 起始点* @return start到所有点的最短距离*/
vector<int> dijkstra(vector<vector<int>> &graph, int start)
{const int INF = 0x3f3f3f3f;  // 经典最大值，松弛其他边不溢出const int num = graph.size();vector<int> distances(num, INF);vector<bool> visited(num, false);distances[start] = 0; // 起始点到自己的距离for (int i = 0; i < num; i++) {// 在未确定到start的最短路的的点里, 找离start最近的点int t = -1;for (int j = 0; j < num; j++) {if (!visited[j] && (t == -1 || graph[j] < graph[t])) {t = j;}}visited[t] = true; // t号点的最短路已确定// 松弛操作，用t号点的更新所有点到start的最短路for (int j = 0; j < num; j++) {distances[j] = min(distances[j], distances[t] + graph[t][j]);}}return distances;
}int main()
{int N = 65536;vector<vector<int>> graph = {{0, 1, 5, N, N, N, N, N, N},{1, 0, 3, 7, 5, N, N, N, N},{5, 3, 0, N, 1, 7, N, N, N},{N, 7, N, 0, 2, N, 3, N, N},{N, 5, 1, 2, 0, 3, 6, 9, N},{N, N, 7, N, 3, 0, N, 5, N},{N, N, N, 3, 6, N, 0, 2, 7},{N, N, N, N, 9, 5, 2, 0, 4},{N, N, N, N, N, N, 7, 4, 0}};vector<int> ans = dijkstra(graph, 0);for (auto &i : ans) {// 0 1 4 7 5 8 10 12 16printf("%d ", i);}return 0;
}