一、核心思想

1. 贪心策略：每次从未确定最短路径的节点中，选择距离源节点最近的节点，将其标记为 “已确定”；

2. 松弛操作：以该节点为中介，更新其邻接节点到源节点的距离；

3. 重复上述步骤，直到所有节点都被标记为 “已确定”。

二、算法步骤（以无向带权图为例）

1. 初始化：

• 距离数组 dist[]：dist[s] = 0（源节点到自身距离为 0），其余节点 dist[i] = ∞（无穷大）；

• 标记数组 visited[]：所有节点初始为 false（未确定最短路径）；

• 优先队列（小顶堆）：存储 (当前距离, 节点)，初始入队 (0, s)。（朴素解法不使用优先队列）

2. 迭代求解：

• 取出优先队列中距离最小的节点 u，若 u 已访问则跳过；

• 标记 u 为已访问（visited[u] = true）；

• 遍历 u 的所有邻接节点 v，若 dist[v] > dist[u] + 权值(u,v)，则更新 dist[v] = dist[u] + 权值(u,v)，并将 (dist[v], v) 入队；

3. 终止条件：优先队列为空，此时 dist[] 数组存储源节点到所有节点的最短路径。（朴素解法不使用优先队列）

三、例子详解

状态表跟踪：我们关注每个点的两个状态：

1. dist[v]：从源点 A 到点 v 的当前已知最短距离估计值。

2. final[v]：该距离是否已确定为最终最短距离（是/否）。

算法每一步：在所有 final 为“否” 的点中，选出 dist 值最小 的一个点进行处理。

第 0 步：初始化

设置 dist[A] = 0，其他点为 ∞。所有点均未确定。

第 1 步：处理节点 A

在所有未确定的点 {A(0), B(∞), C(∞), D(∞), E(∞)} 中，dist 最小的是 A。将其标记为已确定。 检查 A 的所有出边，更新邻居的 dist 值：

• A->B: dist[B] = min(∞, 0+4) = 4

• A->C: dist[C] = min(∞, 0+2) = 2

更新后状态：

第 2 步：处理节点 C

从未确定的点中，dist 最小的是 C(2)。将其标记为已确定。 检查 C 的所有出边，更新未确定邻居的 dist 值：

• C->B: dist[B] = min(4, 2+1) = 3 (更新)

• C->D: dist[D] = min(∞, 2+8) = 10

• C->E: dist[E] = min(∞, 2+10) = 12

更新后状态：

第 3 步：处理节点 B

从未确定的点中，dist 最小的是 B(3)。将其标记为已确定。 检查 B 的所有出边：

• B->C: C 已确定，跳过。

• B->D: dist[D] = min(10, 3+5) = 8 (更新)

更新后状态：

第 4 步：处理节点 D

从未确定的点中，dist 最小的是 D(8)。将其标记为已确定。 检查 D 的所有出边：

• D->E: dist[E] = min(12, 8+2) = 10 (更新)

更新后状态：

第 5 步：处理节点 E

最后一个未确定的点是 E(10)。将其标记为已确定。 检查 E 的出边 E->D，D 已确定，跳过。

最终状态：

最终结果

从源点 A 到各点的最短距离：

• A: 0

• C: 2

• B: 3

• D: 8

• E: 10

过程总结：

1. 初始化所有点的距离 (dist) 和确定状态 (final)。

2. 重复以下步骤，直到所有点 final 为“是”：

   a. 选择：在所有 final 为“否”的点中，选出 dist 值最小的点 u。

   b. 确定：将点 u 的 final 标记为“是”。此时 dist[u] 就是 A 到 u 的最终最短距离。

   c. 松弛：对于 u 的每个邻居 v（且 v 未确定），尝试用 dist[u] + weight(u, v) 去更新 dist[v]，如果更小则更新。

3. 表格中 dist 列的最终值即为最短路径距离。

四、参考代码

1.朴素解法

#include <iostream>  #include <climits>    using namespace std;    const int MAX_N = 100;  // 最大节点数  int graph[MAX_N][MAX_N];  // 邻接矩阵  int dist1[MAX_N];  // 方法1的距离数组  int dist2[MAX_N];  // 方法2的距离数组  bool visited[MAX_N];  // 访问标记数组  int n;  // 实际节点数    // 朴素Dijkstra算法实现（不使用STL）  void dijkstra_naive_no_stl(int src) {      // 初始化      for (int i = 0; i < n; i++) {          dist1[i] = INT_MAX;  // 距离初始化为无穷大          visited[i] = false; // 所有节点都未访问      }            // 源点距离设为0      dist1[src] = 0;            // 需要处理n个节点      for (int i = 0; i < n; i++) {          // 步骤1：在所有未确定的节点中找到距离最小的节点          int u = -1;          int min_dist = INT_MAX;                    for (int j = 0; j < n; j++) {              if (!visited[j] && dist1[j] < min_dist) {                  min_dist = dist1[j];                  u = j;              }          }                    // 如果没有找到可处理的节点（图不连通），提前结束          if (u == -1) break;                    // 步骤2：标记该节点为已确定          visited[u] = true;                    // 步骤3：松弛操作 - 更新所有邻居的距离          for (int v = 0; v < n; v++) {              // 如果u到v有边（graph[u][v] != 0）              if (graph[u][v] != 0 && !visited[v] && dist1[u] != INT_MAX) {                  int new_dist = dist1[u] + graph[u][v];                  if (new_dist < dist1[v]) {                      dist1[v] = new_dist;                  }              }          }      }  }    // 使用邻接矩阵的版本（更朴素）  void dijkstra_adj_matrix(int src) {      // 初始化visited数组      for (int i = 0; i < n; i++) {          visited[i] = false;      }            // 初始化距离数组      for (int i = 0; i < n; i++) {          dist2[i] = graph[src][i] == 0 ? INT_MAX : graph[src][i];      }            dist2[src] = 0;      visited[src] = true;            // 处理剩余的n-1个节点      for (int count = 0; count < n - 1; count++) {          // 找到未访问节点中距离最小的          int u = -1;          int min_dist = INT_MAX;                    for (int i = 0; i < n; i++) {              if (!visited[i] && dist2[i] < min_dist) {                  min_dist = dist2[i];                  u = i;              }          }                    if (u == -1) break;          visited[u] = true;                    // 更新通过u到其他节点的距离          for (int v = 0; v < n; v++) {              if (!visited[v] && graph[u][v] != 0 && dist2[u] != INT_MAX) {                  int new_dist = dist2[u] + graph[u][v];                  if (new_dist < dist2[v]) {                      dist2[v] = new_dist;                  }              }          }      }  }    // 初始化图  void init_graph() {      // 初始化邻接矩阵为0（表示无边）      for (int i = 0; i < MAX_N; i++) {          for (int j = 0; j < MAX_N; j++) {              graph[i][j] = 0;          }      }            // 示例：构建与之前相同的图      n = 5;  // 节点数：A(0), B(1), C(2), D(3), E(4)            // 添加边（使用邻接矩阵表示）      // 注意：这里0表示无边，其他值表示边的权重      graph[0][1] = 4;  // A->B (4)      graph[0][2] = 2;  // A->C (2)            graph[1][2] = 1;  // B->C (1)      graph[1][3] = 5;  // B->D (5)            graph[2][1] = 1;  // C->B (1)      graph[2][3] = 8;  // C->D (8)      graph[2][4] = 10; // C->E (10)            graph[3][4] = 2;  // D->E (2)            graph[4][3] = 2;  // E->D (2)  }    int main() {      // 初始化图      init_graph();            // 从节点0（A）开始计算最短路径      int src = 0;            cout << "方法1：邻接表思路的朴素实现" << endl;      dijkstra_naive_no_stl(src);            cout << "方法2：邻接矩阵的朴素实现" << endl;      dijkstra_adj_matrix(src);            // 输出结果      char node_names[] = {'A', 'B', 'C', 'D', 'E'};            cout << "\n从节点 " << src << " (A) 到各节点的最短距离：" << endl;      cout << "节点\t方法1\t方法2" << endl;      cout << "----------------------" << endl;            for (int i = 0; i < n; i++) {          cout << node_names[i] << "\t";                    if (dist1[i] == INT_MAX) {              cout << "INF";          } else {              cout << dist1[i];          }                    cout << "\t";                    if (dist2[i] == INT_MAX) {              cout << "INF";          } else {              cout << dist2[i];          }                    cout << endl;      }            return 0;  }

2.优先队列解法

#include <iostream>    #include <vector>  #include <queue>  #include <climits>  using namespace std;  typedef pair<int, int> pii;  // 自定义类型别名   /**   * Dijkstra 算法 - 邻接表 + 优先队列版本   *  n 节点数量 (0 ~ n-1)   *  adj 邻接表，adj[u] = vector<{v, w}> 表示 u->v 的边权重为 w   *  src 源点   * 返回： 从源点到所有节点的最短距离   */  vector<int> dijkstra(int n, vector<vector<pii>>& adj, int src) {      vector<int> dist(n, INT_MAX); //距离数组初始化       vector<bool> visited(n, false); //标记数组初始化       priority_queue<pii, vector<pii>, greater<pii>> pq;  // 最小堆（默认按照第一个元素从小到达排序）       dist[src] = 0;      pq.push(make_pair(0, src)); //make_pair自动推导类型       while (!pq.empty()) {          pii current = pq.top(); //优先队列的队头           pq.pop();          int d = current.first; // 从源点到节点 u 的当前最短距离          int u = current.second; // 节点           // 如果这个距离已经过时，跳过          if (d > dist[u]) continue;          // 标记为已访问          visited[u] = true;          // 遍历所有邻居          for (int i = 0; i < adj[u].size(); i++) {              int v = adj[u][i].first; // 获取邻居节点编号              int w = adj[u][i].second; // 获取从 u 到 v 的边权重              if (!visited[v]) {                  int new_dist = dist[u] + w;                  if (new_dist < dist[v]) {                      dist[v] = new_dist;  //更新到v点的距离                       pq.push(make_pair(new_dist, v));//pq中先存距离，再存节点                   }              }          }      }      return dist;  }    int main() {      int n = 5;  // 节点数      vector<vector<pii>> adj(n);      // 构建图      adj[0].push_back(make_pair(1, 4));      adj[0].push_back(make_pair(2, 2));      adj[1].push_back(make_pair(2, 1));      adj[1].push_back(make_pair(3, 5));      adj[2].push_back(make_pair(1, 1));      adj[2].push_back(make_pair(3, 8));      adj[2].push_back(make_pair(4, 10));      adj[3].push_back(make_pair(4, 2));      adj[4].push_back(make_pair(3, 2));            int src = 0;      vector<int> dist = dijkstra(n, adj, src);        cout << "从节点 " << src << " 到各节点的最短距离：" << endl;      for (int i = 0; i < n; i++) {          if (dist[i] == INT_MAX)              cout << i << ": INF" << endl;          else              cout << i << ": " << dist[i] << endl;      }      return 0;  }

注意：

typedef pair<int, int> pii;  // 自定义类型别名     表示自定义类型别名，编程中常用的是  typedef long long ll;   这种

另外，两处first和secod的含义不一样，对于pii来说，只是表示两个int的二元组类型，具体含义是使用者决定的。

3.带路径的迪杰斯特拉算法

#include <iostream>  #include <vector>  #include <queue>  #include <climits>  #include <algorithm> // 用于reverse反转路径  using namespace std;  typedef pair<int, int> pii;  // 自定义类型别名     /**   * Dijkstra 算法 - 邻接表 + 优先队列版本（带路径记录）   *  n 节点数量 (0 ~ n-1)   *  adj 邻接表，adj[u] = vector<{v, w}> 表示 u->v 的边权重为 w   *  src 源点   *  path 输出参数：path[v] 存储节点v的前驱节点（用于回溯路径）   * 返回： 从源点到所有节点的最短距离   */  vector<int> dijkstra(int n, vector<vector<pii>>& adj, int src, vector<int>& path) {      vector<int> dist(n, INT_MAX); // 距离数组：src到各节点的最短距离      vector<bool> visited(n, false); // 标记节点是否已确定最短距离      priority_queue<pii, vector<pii>, greater<pii>> pq;  // 最小堆（按距离升序）        // 初始化：路径数组初始化为-1（表示无前置节点）      path.assign(n, -1);      dist[src] = 0;      pq.push(make_pair(0, src));         while (!pq.empty()) {          pii current = pq.top();           pq.pop();          int d = current.first; // 源点到u的当前距离          int u = current.second; // 当前节点            // 距离过时，跳过（已找到更短路径）          if (d > dist[u]) continue;          visited[u] = true;            // 遍历u的所有邻居          for (int i = 0; i < adj[u].size(); i++) {              int v = adj[u][i].first; // 邻居节点              int w = adj[u][i].second; // 边权重              if (!visited[v]) {                  int new_dist = dist[u] + w;                  // 找到更短路径：更新距离 + 记录前驱节点                  if (new_dist < dist[v]) {                      dist[v] = new_dist;                      path[v] = u; // 记录v的前驱是u                      pq.push(make_pair(new_dist, v));                  }              }          }      }      return dist;  }    /**   * 回溯路径：从目标节点target反向找到源点src，再反转得到正序路径   *  src 源点   *  target 目标节点   *  path 前驱节点数组   * 返回： src到target的最短路径（正序）   */  vector<int> getShortestPath(int src, int target, const vector<int>& path) {      vector<int> res;      // 若目标节点不可达，返回空路径      if (path[target] == -1 && src != target) {          return res;      }      // 从target回溯到src      for (int cur = target; cur != -1; cur = path[cur]) {          res.push_back(cur);      }      // 反转得到正序路径（src -> ... -> target）      reverse(res.begin(), res.end());      return res;  }    int main() {      int n = 5;  // 节点数（0~4）      vector<vector<pii>> adj(n);      // 构建图      adj[0].push_back(make_pair(1, 4));      adj[0].push_back(make_pair(2, 2));      adj[1].push_back(make_pair(2, 1));      adj[1].push_back(make_pair(3, 5));      adj[2].push_back(make_pair(1, 1));      adj[2].push_back(make_pair(3, 8));      adj[2].push_back(make_pair(4, 10));      adj[3].push_back(make_pair(4, 2));      adj[4].push_back(make_pair(3, 2));            int src = 0;      vector<int> path; // 存储各节点的前驱节点      vector<int> dist = dijkstra(n, adj, src, path);        // 输出最短距离 + 最短路径      cout << "从节点 " << src << " 到各节点的最短距离和路径：" << endl;      for (int i = 0; i < n; i++) {          cout << "节点 " << i << "：";          if (dist[i] == INT_MAX) {              cout << "INF（无路径）" << endl;          } else {              cout << "距离=" << dist[i] << "，路径：";              vector<int> shortest_path = getShortestPath(src, i, path);              // 输出路径              for (int j = 0; j < shortest_path.size(); j++) {                  if (j > 0) cout << " -> ";                  cout << shortest_path[j];              }              cout << endl;          }      }      return 0;  }    /*    从节点 0 到各节点的最短距离和路径：  节点 0：距离=0，路径：0  节点 1：距离=3，路径：0 -> 2 -> 1  节点 2：距离=2，路径：0 -> 2  节点 3：距离=8，路径：0 -> 2 -> 1 -> 3  节点 4：距离=10，路径：0 -> 2 -> 1 -> 3 -> 4      */

1.path 数组：  类型：vector<int>，path[v] = u 表示 “到达节点 v 的最短路径中，v 的上一个节点是 u”；  初始化：所有元素设为 -1（表示无前置节点，源点的前驱始终为 -1）；  更新逻辑：当找到节点 v 的更短路径时，同步更新 path[v] = u（u 是当前节点）。

2.getShortestPath 函数：  功能：从目标节点 target 反向回溯到源点 src（通过 path 数组）；  处理：回溯得到的路径是逆序（target -> ... -> src），需用 reverse 反转得到正序路径；  边界：若 path[target] == -1 且 target != src，说明目标节点不可达，返回空路径。