Click here to Skip to main content
14,599,199 members
Rate this:
Please Sign up or sign in to vote.
See more:
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);
		}
	}
}


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?
Posted

1 solution

Rate this:
Please Sign up or sign in to vote.

Solution 1

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...
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100