Djikstra 的算法

### Dijkstra算法概述 Dijkstra算法是一种经典的图论算法，专门用于解决单源最短路径问题。该算法由荷兰计算机科学家Edsger W. Dijkstra于1956年提出[^1]。 #### 算法适用范围 此算法适用于带权重的有向图或无向图，在这些图形结构中寻找从一个特定起点出发到达其余各点之间的最短距离。值得注意的是，对于存在负边权的情况，不建议采用Dijkstra算法来求解最短路径问题；此时应考虑Bellman-Ford等其他更适合处理此类情况的方法[^2]。 #### 基本思路与流程描述 核心思想在于通过贪心策略逐步构建已知最优解集合S，并不断更新候选节点集Q内的估计值直至遍历完整张网络为止： - 初始化阶段设定起始结点v0的距离d[v0]=0, 同时将其余所有未访问过的顶点初始化为无穷大； - 将当前最近的一个尚未加入到最终结果里的位置u纳入集合S当中； - 对每一个邻接于新成员u却仍留在待定区域外侧w执行松弛操作：如果经由u前往w所花费的成本小于之前记录下的最小开销，则替换旧数据并标记前驱关系以便后续回溯路线； - 反复迭代上述过程直到全部目标都被收录进来或者不存在更优的选择对象为止。 #### C语言实现示例 以下是基于优先队列优化版本的C语言代码片段展示如何运用Dijkstra方法计算给定点至其它任意可达终点间的最短行程长度: ```c #include <stdio.h> #include <stdlib.h> #define MAX_V 1000 // 节点数量上限 #define INF (1 << 30) // 表达极大数作为初始未知状态 typedef struct { int v; /* 邻居 */ int cost; /* 边上的代价 */ } Edge; int n; /* 结点总数 */ Edge M[MAX_V]; /* 存储每条边的信息 */ void dijkstra(int s){ ... } ``` 由于篇幅原因省略部分细节，请参照相关资料完成整个函数定义。 #### C++ 实现案例分享 下面给出一段完整的C++程序用来演示怎样利用STL容器priority_queue加速查找效率从而高效地解决问题实例: ```cpp #include<bits/stdc++.h> using namespace std; const long long inf=LLONG_MAX/2; struct node{ int to,cost; }; vector<node> G[100]; bool vis[100]={false}; long long dis[100]; void dijkstra(int start){ priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> q; fill(dis,dis+100,inf); memset(vis,false,sizeof(vis)); dis[start]=0;q.push(make_pair(0,start)); while(!q.empty()){ pair<int,int> p=q.top();q.pop(); int u=p.second; if(vis[u]) continue; vis[u]=true; for(auto e:G[u]){ if(dis[e.to]>dis[u]+e.cost){ dis[e.to]=dis[u]+e.cost; q.push({dis[e.to],e.to}); } } } } int main(){ int m,n,s,t,w; cin>>n>>m; for(int i=0;i<m;++i){ scanf("%d%d%d",&s,&t,&w); G[s].push_back((node){t,w}); } dijkstra(1); for(int i=1;i<=n;++i) printf("From %d to %d :%lld\n",1,i,dis[i]==inf?-1:dis[i]); return 0; } ``` 这段代码实现了读取输入、建立图模型以及调用`dijkstra()`来进行最短路查询的功能。 #### Java 版本的应用实践 最后附上一份简洁明了的Java版解决方案供学习交流之用： ```java import java.util.*; public class Main { static final int N = 100005; static List<List<Node>> adjList = new ArrayList<>(); static boolean[] visited = new boolean[N]; static int[] dist = new int[N]; public static void main(String args[]) throws Exception { Scanner sc = new Scanner(System.in); int V = sc.nextInt(), E = sc.nextInt(); for (int i = 0; i <= V; ++i) { adjList.add(new ArrayList<>()); } for (int i = 0; i < E; ++i) { int from = sc.nextInt(), to = sc.nextInt(), weight = sc.nextInt(); adjList.get(from).add(new Node(to, weight)); } Arrays.fill(dist, Integer.MAX_VALUE / 2); dijkstra(V,E,adjList,dist,visited); for (int i = 1; i <= V ; i++) System.out.println(i+" "+dist[i]); } private static void dijkstra(int verticesCount ,int edgesCount,List<List<Node>> adjacencyLists, int[] distancesToVertices,boolean[] vertexVisitStatuses ) { PriorityQueue<Node> pq = new PriorityQueue<>(verticesCount, Comparator.comparingInt(o -> o.distance)); distancesToVertices[1] = 0; pq.offer(new Node(1, 0)); while (!pq.isEmpty()) { Node currentNode = pq.poll(); if(vertexVisitStatuses[currentNode.vertexIndex]) continue; vertexVisitStatuses[currentNode.vertexIndex] = true; for(Node neighbor : adjacencyLists.get(currentNode.vertexIndex)){ if(distancesToVertices[neighbor.vertexIndex] > distancesToVertices[currentNode.vertexIndex] + neighbor.distance){ distancesToVertices[neighbor.vertexIndex] = distancesToVertices[currentNode.vertexIndex] + neighbor.distance; pq.offer(new Node(neighbor.vertexIndex, distancesToVertices[neighbor.vertexIndex])); } } } } record Node(int vertexIndex, int distance){} } ``` 以上就是关于Dijkstra算法的一些基本概念及其不同编程语言环境下的具体编码方式[^3]。