I am trying to use Dijkstra's algorithm to find the shortest path from a specific vertex (v0) to the rest of them. That is solved and works well with this code from this link below: http://en.literateprograms.org/index.php?title=Special:DownloadCode/Dijkstra%27s_algorithm_(Java)&oldid=15444
I am having trouble with assigning the Edge array in a for loop from the user input, as opposed to hard-coding it like it is here.
Any help assigning a new edge to Edge[] adjacencies from each vertex? Keeping in mind it could be 1 or multiple edges.
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 static void main(String[] args)
{
Vertex v[] = new Vertex[3];
Vertex v[0] = new Vertex("Harrisburg");
Vertex v[1] = new Vertex("Baltimore");
Vertex v[2] = new Vertex("Washington");
v0.adjacencies = new Edge[]{ new Edge(v[1], 1),
new Edge(v[2], 3) };
v1.adjacencies = new Edge[]{ new Edge(v[0], 1),
new Edge(v[2], 1),};
v2.adjacencies = new Edge[]{ new Edge(v[0], 3),
new Edge(v[1], 1) };
Vertex[] vertices = { v0, v1, v2};
/*Three vertices with weight: V0 connects (V1,1),(V2,3)
V1 connects (V0,1),(V2,1)
V2 connects (V1,1),(V2,3)
*/
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 above code works well in finding the shortest path from v0 to all the other vertices. The problem occurs when assigning the new edge[] to edge[] adjacencies.
For example this does not produce the correct output:
for (int i = 0; i < total_vertices; i++){
s = br.readLine();
char[] line = s.toCharArray();
for (int j = 0; j < line.length; j++){
if(j % 4 == 0 ){ //Input: vertex weight vertex weight: 1 1 2 3
int vert = Integer.parseInt(String.valueOf(line[j]));
int w = Integer.parseInt(String.valueOf(line[j+2]));
v[i].adjacencies = new Edge[] {new Edge(v[vert], w)};
}
}
}
As opposed to this:
v0.adjacencies = new Edge[]{ new Edge(v[1], 1),
new Edge(v[2], 3) };
How can I take the user input and make an Edge[], to pass it to adjacencies? The problem is it could be 0 edges or many.
Any help would be much appreciated
Thanks!
