Java中Dijkstra算法需要帮助 [英] Help Needed on Dijkstra Algorithm in Java

问题描述

我很难理解这些代码。

Hi, I have difficulty understanding these code.

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) {
		Vertex v0 = new Vertex("Harrisburg");
		Vertex v1 = new Vertex("Baltimore");
		Vertex v2 = new Vertex("Washington");
		Vertex v3 = new Vertex("Philadelphia");
		Vertex v4 = new Vertex("Binghamton");
		Vertex v5 = new Vertex("Allentown");
		Vertex v6 = new Vertex("New York");
		v0.adjacencies = new Edge[] { new Edge(v1, 79.83), new Edge(v5, 81.15) };
		v1.adjacencies = new Edge[] { new Edge(v0, 79.75), new Edge(v2, 39.42),
				new Edge(v3, 103.00) };
		v2.adjacencies = new Edge[] { new Edge(v1, 38.65) };
		v3.adjacencies = new Edge[] { new Edge(v1, 102.53),
				new Edge(v5, 61.44), new Edge(v6, 96.79) };
		v4.adjacencies = new Edge[] { new Edge(v5, 133.04) };
		v5.adjacencies = new Edge[] { new Edge(v0, 81.77), new Edge(v3, 62.05),
				new Edge(v4, 134.47), new Edge(v6, 91.63) };
		v6.adjacencies = new Edge[] { new Edge(v3, 97.24), new Edge(v5, 87.94) };
		Vertex[] vertices = { v0, v1, v2, v3, v4, v5, v6 };

		computePaths(v0);
		for (Vertex v : vertices) {
			System.out.println("Distance to " + v + ": " + v.minDistance);
			List<Vertex> path = getShortestPathTo(v);
			System.out.println("Path: " + path);
		}
	}
}

main方法中的部分computePaths（v0）; < br $>


v0是来源，如果我想继续并找到v1'到达所有目的地的最短路径，我所做的就是复制相同的for循环和将源更改为v1。



这就是我所做的，但它不起作用，因为它仍然获得v0的最短路径。 br $> b $ b

The part in the main method computePaths(v0);

v0 is the source, and if i want to continue and find v1''s shortest path to all destination, what i have done is by copying the same for loop and change the source to "v1".

This is what i have done, but it does not work as it is still obtaining the v0''s shortest path.

computePaths(v1);
		for (Vertex v : vertices) {
			System.out.println("Distance to " + v + ": " + v.minDistance);
			List<Vertex> path = getShortestPathTo(v);
			System.out.println("Path: " + path);

能帮助我解决这个问题的任何一种灵魂？

Any kind souls able to help me fix this issue?

推荐答案

看看在算法的文字描述中可以找到这里 [ ^ ]带有一些不错的动画。



如果您不喜欢这种解释，Google非常乐于助人......

Have a look at the text description of the algorithm, which can be found here[^] with some nice animation.

If you don''t like that explanation, Google is quite helpful...

这篇关于Java中Dijkstra算法需要帮助的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！