951-迪杰斯特拉算法C++实现

#include 
#include 
#include 
using namespace std;#if 0
using uint = unsigned int;
const uint INF = INT_MAX;#if 0
// 迪杰斯特拉算法接口
int Dijkstra(vector<vector<uint>>& graph,int start,  // 起点 int end)    // 终点
{const int N = graph.size();// 存储各个顶点的最短路径(最小权值)vector<uint> dis(N, 0);vector<bool> use(N, false);// 把start放入S集合use[start] = true;// 初始化start到其它U集合顶点权值for (int i = 0; i < N; i++){dis[i] = graph[start][i];}// 把U集合中的顶点处理完  for (int i = 1; i < N; i++)    // O(n){// 先从U集合中找到权值最小的顶点   int k = -1;int min = INF;for (int j = 0; j < N; j++)  // O(n){if (!use[j] && min > dis[j]) // U集合的顶点{min = dis[j];k = j;}}if (k == -1){break;}// 把选出的顶点加入到S集合中use[k] = true;// 把U集合中剩余顶点的权值信息更新一下for (int j = 0; j < N; j++){if (!use[j] && min + graph[k][j] < dis[j]) // U集合{dis[j] = min + graph[k][j];}}}// 测试打印for (int d : dis){cout << d << " ";}cout << endl;return dis[end];
}
#endif// 迪杰斯特拉算法接口-优化
int Dijkstra(vector<vector<uint>>& graph,int start,  // 起点 int end)    // 终点
{const int N = graph.size();// 存储各个顶点的最短路径(最小权值)vector<uint> dis(N, 0);vector<bool> use(N, false);// 定义小根堆priority_queue<pair<uint, int>, vector<pair<uint, int>>, greater<pair<uint, int>>> que;// 把start放入S集合use[start] = true;// 初始化start到其它U集合顶点权值for (int i = 0; i < N; i++){dis[i] = graph[start][i];// 把除start顶点的其它顶点全部放入U集合小根堆中if (i != start){que.emplace(graph[start][i], i);}}// 把U集合中的顶点处理完  while (!que.empty())    // O(n){// 用小根堆找权值最小的顶点    O(logn)   pair<权值，顶点编号>// 先从U集合中找到权值最小的顶点   auto pair = que.top();que.pop();if (pair.first == INF){break;}int k = pair.second;int min = pair.first;if (use[k])  continue;// 把选出的顶点加入到S集合中use[k] = true;// 把U集合中剩余顶点的权值信息更新一下for (int j = 0; j < N; j++){if (!use[j] && min + graph[k][j] < dis[j]) // U集合{dis[j] = min + graph[k][j];// 更新U集合中顶点的权值！que.emplace(dis[j], j);}}}// 测试打印for (int d : dis){cout << d << " ";}cout << endl;return dis[end];
}int main()
{vector<vector<uint>> graph ={{0, 6, 3, INF, INF, INF},{6, 0, 2, 5, INF, INF},{3, 2, 0, 3, 4, INF},{INF, 5, 3, 0, 2, 3},{INF, INF, 4, 2, 0, 5},{INF, INF, INF, 3, 5, 0},};int distance = Dijkstra(graph, 0, 1);if (distance == INF){cout << "不存在有效路径!" << endl;}else{cout << "distance:" << distance << endl;}
}
#endif

#include 
#include 
using namespace std;using uint = unsigned int;
const uint INF = INT_MAX;int main()
{vector<vector<uint>> graph ={{0, 6, 3, INF, INF, INF},{6, 0, 2, 5, INF, INF},{3, 2, 0, 3, 4, INF},{INF, 5, 3, 0, 2, 3},{INF, INF, 4, 2, 0, 5},{INF, INF, INF, 3, 5, 0},};// 一次把每一个顶点加入for (int k = 0; k < graph.size(); k++){// 都需要遍历邻接矩阵for (int i = 0; i < graph.size(); i++){for (int j = 0; j < graph.size(); j++){graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j]);}}}for (auto line : graph){for (auto dis : line){cout << dis << " ";}cout << endl;}// cout << graph[start][end] << endl;
}