Java中如何实现Dijkstra算法寻找最短路径？

本文共计3173个文字，预计阅读时间需要13分钟。

定义最短路径问题的定义为：设 \( G=(V, E) \) 为连通图，图中的每一边 \((v_i, v_j)\) 有权 \( l_{ij} \)，若 \( l_{ij}=\infty \)，表示 \((v_i, v_j)\) 之间没有边，求图中任意两点 \( (v_s, v_t) \) 之间的一条路径 \((\mu)\)，使得该路径的总权值最小。

定义

最短路问题的定义为：设 \(G=(V,E)\) 为连通图，图中各边 \((v_i,v_j)\) 有权 \(l_{ij}\) （\(l_{ij}=\infty\) 表示 \(v_i,v_j\) 间没有边） ，\(v_s,v_t\) 为图中任意两点，求一条道路 \(\mu\)，使得它是从 \(v_s\) 到 \(v_t\) 的所有路中总权最小的路，即：\(L(\mu)=\sum_{(v_i,v_j)\in \mu}l_{ij}\) 最小。

下图左侧是一幅带权有向图，以顶点 0 为起点到各个顶点的最短路径形成的最短路径树如下图右侧所示：

带权有向图的实现

在实现最短路算法之前需要先实现带权有向图。在上一篇博客 《如何在 Java 中实现最小生成树算法》 中我们实现了带权无向图，只需一点修改就能实现带权有向图。

带权有向边

首先应该实现带权有向图中的边 DirectedEdge，这个类有三个成员变量：指出边的顶点 v、边指向的顶点 w 和边的权重 weight。