就像SplinterReality所说：
There's no reason not to use Dijkstra's algorithm here.
下面的代码我从这里开始进行了昵称，并对其进行了修改以解决问题中的示例。
import java.util.PriorityQueue;import java.util.List;import java.util.ArrayList;import java.util.Collections;class Vertex implements Comparable<Vertex>{ public final String name; public Edge[] adjacencies; public double minDistance = Double.POSITIVE_INFINITY; public Vertex previous; public Vertex(String argName) { name = argName; } public String toString() { return name; } public int compareTo(Vertex other) { return Double.compare(minDistance, other.minDistance); }}class Edge{ public final Vertex target; public final double weight; public Edge(Vertex argTarget, double argWeight) { target = argTarget; weight = argWeight; }}public class Dijkstra{ public static void computePaths(Vertex source) { source.minDistance = 0.; PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>(); vertexQueue.add(source); while (!vertexQueue.isEmpty()) { Vertex u = vertexQueue.poll(); // Visit each edge exiting u for (Edge e : u.adjacencies) { Vertex v = e.target; double weight = e.weight; double distanceThroughU = u.minDistance + weight; if (distanceThroughU < v.minDistance) { vertexQueue.remove(v); v.minDistance = distanceThroughU ; v.previous = u; vertexQueue.add(v); } } } } public static List<Vertex> getShortestPathTo(Vertex target) { List<Vertex> path = new ArrayList<Vertex>(); for (Vertex vertex = target; vertex != null; vertex = vertex.previous) path.add(vertex); Collections.reverse(path); return path; } public static void main(String[] args) { // mark all the vertices Vertex A = new Vertex("A"); Vertex B = new Vertex("B"); Vertex D = new Vertex("D"); Vertex F = new Vertex("F"); Vertex K = new Vertex("K"); Vertex J = new Vertex("J"); Vertex M = new Vertex("M"); Vertex O = new Vertex("O"); Vertex P = new Vertex("P"); Vertex R = new Vertex("R"); Vertex Z = new Vertex("Z"); // set the edges and weight A.adjacencies = new Edge[]{ new Edge(M, 8) }; B.adjacencies = new Edge[]{ new Edge(D, 11) }; D.adjacencies = new Edge[]{ new Edge(B, 11) }; F.adjacencies = new Edge[]{ new Edge(K, 23) }; K.adjacencies = new Edge[]{ new Edge(O, 40) }; J.adjacencies = new Edge[]{ new Edge(K, 25) }; M.adjacencies = new Edge[]{ new Edge(R, 8) }; O.adjacencies = new Edge[]{ new Edge(K, 40) }; P.adjacencies = new Edge[]{ new Edge(Z, 18) }; R.adjacencies = new Edge[]{ new Edge(P, 15) }; Z.adjacencies = new Edge[]{ new Edge(P, 18) }; computePaths(A); // run Dijkstra System.out.println("Distance to " + Z + ": " + Z.minDistance); List<Vertex> path = getShortestPathTo(Z); System.out.println("Path: " + path); }}上面的代码产生：
Distance to Z: 49.0Path: [A, M, R, P, Z]
