1 Title
Given a weighted graph and a starting vertex, find the shortest path from that starting vertex to all other vertices in the graph.
给定一个加权图和一个起始顶点，要找到从该起始顶点到图中所有其他顶点的最短路径。
2 Analysis
基本思想：
- 一个顶点属于集合S，当且仅当从源到该顶点的最短路径长度已知。
- 设置顶点集合S，并不断地作贪心选择来扩充这个集合。
- 贪心策略：每次都从V-S中找出具有最短特殊路长的顶点u加入S。
用一个 dist 数组保存源点到其余各个节点的距离，dist[i] 表示源点到节点 i 的距离。初始时，dist 数组的各个元素为无穷大。用一个状态数组 final 记录是否找到了源点到该节点的最短距离，final[i] 如果为真，则表示找到了源点到节点 i 的最短距离，final[i] 如果为假，则表示源点到节点 i 的最短距离还没有找到。初始时，final 各个元素为假。
计算过程：从1号节点出发，置1号节点的dist为0，final为True；遍历表格寻找dist最小的节点，此时为1号节点，则将1号节点所有直接能到达的节点，对应的dist和pre进行修改(例题中为2，3，4号，则修改2，3，4号节点的dist，dist的值应该加上1号节点的dist值0，pre为1号)；然后遍历表格寻找dist最小且final为false的节点，将该节点的final修改为True，则将4号节点所有能到达的节点，对应的dist和pre进行修改，倘若能到达的节点dist已经有值，则需要进行对比，将较小的填入；后续操作如上。（注dist的值修改时应加入前置节点的dist值）。
3 Code
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;#define INF INT_MAX //infinity
void dijkstra(int n, vector<vector<int>> graph, int start) {vector<int> dist(n, INF); // Store the shortest path from the source point to each nodevector<int> pre(n, -1); // The precursor node that stores the shortest pathvector<bool> final(n, false); // Marks whether the node is accesseddist[start] = 0;for (int i = 0; i < n - 1; i++) {int u = -1;for (int j = 0; j < n; j++) {if (!final[j] && (u == -1 || dist[j] < dist[u])) {u = j;}}final[u] = true;//Adds node u to the accessed collectionfor (int v = 0; v < n; v++) {//Update the shortest path of the node adjacent to uif (graph[u][v] != INF && !final[v] && dist[u] + graph[u][v] < dist[v]) {dist[v] = dist[u] + graph[u][v];// Update the shortest pathpre[v] = u;// Update the precursor node}}}
}int main() {int n, e;cout << "Enter the number of vertices: ";cin >> n;// 使用vector创建邻接矩阵vector<vector<int>> graph(n, vector<int>(n, INF));for (int i = 0; i < n; i++) {graph[i][i] = 0;//自己到自己的权重为 0}cout << "Enter the number of edges: ";cin >> e;cout << "Enter the edges (u, v, weight):\n";for (int i = 0; i < e; i++) {int u, v, weight;cin >> u >> v >> weight;// 调整输入为从1开始的索引graph[u - 1][v - 1] = weight;}int start;cout << "Enter the source node (1-based index): ";cin >> start;start--; // 转换为0-based索引//prim(n, graph); // 调用 Prim 算法dijkstra(n, graph, start);return 0;
}4 Time Complexity
在每次循环中，我们选择未访问的节点中距离源点最近的节点，这一操作的时间复杂度是 O(n) 。更新相邻节点的最短路径也需要遍历所有 n 个邻接节点，时间复杂度为 O(n) 。总共会进行 n 次这样的操作，因此时间复杂度为 O(n^2) ，这是因为每次都要线性扫描所有节点来找最小值。
5 Space Complexity
邻接矩阵graph：O(n^2) 。dist、pre 和 visited 数组：每个数组占用 O(n) 空间。因此，空间复杂度为O(n^2) ，这是由邻接矩阵的存储方式决定的。