本文共 1465 字，大约阅读时间需要 4 分钟。
Dijkstra算法是用来在有向图中找到一个顶点到其余顶点的最短路径的算法。它的基本思想是通过不断地更新源点到其余顶点的最短路径，逐步找到所有顶点的最短路径。
Dijkstra算法的主要操作可以分为两步：第一步是从源点出发，选取当前到达其余顶点路径最短的那个顶点并加入已处理的集合中；第二步是每次选取一个顶点后，都要更新源点到其余顶点的最短路径，因为加入新的顶点可能会提供更短的路径。
与Prim算法相比，Dijkstra算法的核心思想在于记录的是源点到其余顶点的最短路径，而Prim算法记录的是其余顶点到当前顶点的最短路径。这种区别导致了两个算法在实现时的细节差异。
下面我们来看一个具体的例子。假设顶点0是源点，首先会选取与顶点0相连的顶点进行比较。由于之前这些顶点的最短路径都是未知的（如1、3、4），所以会更新它们的最短路径距离。接着，选出路径最短的顶点（通常是1），并更新其余顶点的最短路径。重复这个过程直到所有顶点的最短路径都被确定。
以下是用C语言实现的Dijkstra算法代码示例：
#include#include #include using namespace std;void Dijkstra(int n, int s, int G[n][n]) { int d[n]; bool vis[n]; fill(d, d + n, INF); d[s] = 0; vis[s] = true; for(int i = 0; i < n; i++) { int u = -1; int min_dist = INF; for(int j = 0; j < n; j++) { if(!vis[j] && d[j] < min_dist) { u = j; min_dist = d[j]; } } if(u == -1) break; vis[u] = true; for(int v = 0; v < n; v++) { if(!vis[v] && G[u][v] != INF && d[u] + G[u][v] < d[v]) { d[v] = d[u] + G[u][v]; } } }}int main() { int n, m, s; cin >> n >> m >> s; int G[n][n] = {INF}; for(int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; G[u][v] = w; } Dijkstra(n, s, G); for(int i = 0; i < n; i++) { cout << d[i] << " "; }}
这个代码实现了Dijkstra算法的主要逻辑：初始化源点的距离为0，其他顶点的距离为无穷大；通过不断地更新和选择当前最短路径的顶点，最终得到源点到其余顶点的最短路径。
转载地址：http://krwg.baihongyu.com/