Here is my implementation of Dijkstra, based on pseudocode provided in class. (This was a school assignment, but the project has already been turned in by a teammate. I'm just trying to figure out why my version does not work.)
When I create my own graph with the same graph info as the txt file, it gives me the correct output- the shortest path to each vertex from a given source. When I read in a text file, it does not. It reads in the file and prints the correct adjacency list, but does not give the shortest paths.
Here's where it goes wrong when it runs on the file: on the first iteration of relax, it updates the adjacent vertex distances and parent, but returns to the dijkstra method and the distance/parent are no longer updated. Why is that?
The provided txt file looks like this:
4
0 1,1 3,2
1 2,4
2 1,6 4,7
3 0,3 1,9 2,2
4 0,10 3,5
Sorry if this is a mess, I'm learning!
import java.util.PriorityQueue;
import java.util.Collections;
import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.io.IOException;
/** Class to implement Dijkstra algorithm.
* Includes classes for Vertex, Edge and Graph.
*/
public class Dijkstra {
private LinkedList<Vertex> shortestPath;
private LinkedList<Vertex> path;
private PriorityQueue<Vertex> pq;
private PriorityQueue<Vertex> pq2;
static final int INFINITY = Integer.MAX_VALUE;
/** Main method reads in a txt file and prints
* the shortest path to each vertex from a given source.
* @throws FileNotFoundException
* @throws IOException
*/
public static void main(String[] args) throws FileNotFoundException,
IOException {
// ourGraph is a sample graph to test output
// vertices and edges are the same as txt file
Vertex v0 = new Vertex("0");
Vertex v1 = new Vertex("1");
Vertex v2 = new Vertex("2");
Vertex v3 = new Vertex("3");
Vertex v4 = new Vertex("4");
Graph ourGraph = new Graph(v4);
ourGraph.addVertex(v0);
ourGraph.addVertex(v1);
ourGraph.addVertex(v2);
ourGraph.addVertex(v3);
ourGraph.addVertex(v4);
ourGraph.addEdge(v0, v1, 1);
ourGraph.addEdge(v0, v3, 2);
ourGraph.addEdge(v1, v2, 4);
ourGraph.addEdge(v2, v1, 6);
ourGraph.addEdge(v2, v4, 7);
ourGraph.addEdge(v3, v0, 3);
ourGraph.addEdge(v3, v1, 9);
ourGraph.addEdge(v3, v2, 2);
ourGraph.addEdge(v4, v0, 10);
ourGraph.addEdge(v4, v3, 5);
ourGraph.printGraph(); // prints correct output
Dijkstra d = new Dijkstra();
d.getDijkstra(ourGraph, v4); // runs Dijkstra with v4 as source
for (Vertex v : ourGraph.nodes) {
d.printShortestPath(ourGraph, v); // correct output for shortest paths
}
Scanner scanner = new Scanner(System.in);
System.out.print("Please enter file name: ");
String fileName = scanner.nextLine();
Scanner file = new Scanner(new File(fileName));
String sourceID = file.nextLine();
Graph g = new Graph(new Vertex(sourceID));
while (file.hasNext()) {
String[] currentLine = file.nextLine().split(" |,");
Vertex vertex = new Vertex(currentLine[0]);
g.addVertex(vertex);
// set the graph's source vertex
if (vertex.getName().equals(sourceID)) {
g.source = vertex;
}
// read current line for adjacent vertices and their edge weights
for (int i = 1; i < currentLine.length; i ) {
g.addEdge(vertex, new Vertex(currentLine[i]),
Integer.parseInt(currentLine[ i]));
}
}
g.printGraph(); // prints expected graph
Dijkstra d2 = new Dijkstra();
d2.getDijkstra(g, g.source);
for (Vertex vx : g.nodes) {
d2.printShortestPath(g, vx);
}
}
/* Vertex class with fields for name, parent,
* distance, and edge list.
*/
static class Vertex implements Comparable<Vertex> {
private String name;
private Vertex p;
private int d;
private LinkedList<Edge> edgeList;
Vertex(String n) {
this.name = n;
this.p = null;
this.d = INFINITY;
edgeList = new LinkedList<>();
}
public String getName() {
return name;
}
public LinkedList<Edge> getEdges() {
return edgeList;
}
@Override
public int compareTo(Vertex other) {
return Integer.compare(this.d, other.d);
}
}
static class Edge {
private int weight;
private Vertex source;
private Vertex destination;
Edge(Vertex d, int w) {
this.destination = d;
this.weight = w;
}
public int getWeight() {
return weight;
}
public Vertex getSource() {
return source;
}
public Vertex getDestination() {
return destination;
}
}
static class Graph {
private LinkedList<Vertex> nodes;
private Vertex source;
Graph(Vertex s) {
nodes = new LinkedList<>();
this.source = s;
}
public void addSource(Vertex s) {
this.source = s;
}
public void addEdge(Vertex s, Vertex d, int weight) {
s.getEdges().add(new Edge(d, weight));
}
public void addVertex(Vertex v) {
nodes.add(v);
}
public void printGraph() {
for (Vertex v : nodes) {
System.out.print("vertex: " v.getName() ": ");
for (Edge e : v.getEdges()) {
System.out.print(e.getDestination().getName()
"," e.getWeight() " ");
}
System.out.print("\n");
}
}
}
/** method to calculate shortest path using
* Dijkstra's algorithm.
* @param graph with vertices and edges
* @param source as starting vertex
* @return a LinkedList of vertices as shortest path
*/
public LinkedList<Vertex> getDijkstra(Graph graph, Vertex source) {
initializeSingleSource(graph, source);
shortestPath = new LinkedList<Vertex>();
pq = new PriorityQueue<Vertex>();
pq.addAll(graph.nodes);
while (!pq.isEmpty()) {
// used a second pq to re-min-heapify after min is removed
pq2 = new PriorityQueue<Vertex>();
pq2.addAll(pq);
Vertex u = pq2.poll();
if (!shortestPath.contains(u)) {
shortestPath.add(u);
}
for (Edge e : u.getEdges()) {
relax(u, e.getDestination(), e.getWeight());
}
pq.remove(u);
}
return shortestPath;
}
/** initializes each vertex distance to infinity and
* each parent to null. Sets source distance to 0.
* @param graph for input
* @param source is source vertex of graph
*/
public void initializeSingleSource(Graph graph, Vertex source) {
for (Vertex v : graph.nodes) {
v.d = INFINITY;
}
source.d = 0;
}
/** Relax checks if the distance of the destination
* vertex is greater than the distance of the start plus
* the edge weight and updates distance and parent attributes.
* @param u vertex is start
* @param v is destination vertex
* @param weight is edge weight
*/
public void relax(Vertex u, Vertex v, int weight) {
if (v.d > u.d weight) {
v.d = u.d weight;
v.p = u;
}
}
/** getPath puts shortest path in order for a given target.
* @param g for graph input
* @param target is target vertex of shortest path from the
* graph's source
* @return LinkedList of shortest path
*/
public LinkedList<Vertex> getPath(Graph g, Vertex target) {
LinkedList<Vertex> path = new LinkedList<Vertex>();
Vertex step = target;
int i = shortestPath.indexOf(step);
while (step.p != null) {
path.add(step);
step = step.p;
}
Collections.reverse(path);
return path;
}
/** prints a formatted list of a single vertex's shortest path.
* from the graph's source
* @param g is graph
* @param target is target vertex of shortest path
*/
public void printShortestPath(Graph g, Vertex target) {
shortestPath = getPath(g, target);
System.out.print(target.getName() ": ");
for (Vertex v : shortestPath) {
System.out.print(v.getName() " ");
}
System.out.print("\n");
}
}
CodePudding user response：
First the structure of the file is as follows:
4
0 1,1 3,2
1 2,4
2 1,6 4,7
3 0,3 1,9 2,2
4 0,10 3,5
Now for your problem here, the cause of this problem is the creation of new vertices when reading the file:
while (file.hasNext()) {
String[] currentLine = file.nextLine().split(" |,");
Vertex vertex = new Vertex(currentLine[0]);
g.addVertex(vertex);
// set the graph's source vertex
if (vertex.getName().equals(sourceID)) {
g.source = vertex;
}
// read current line for adjacent vertices and their edge weights
for (int i = 1; i < currentLine.length; i ) {
g.addEdge(vertex, new Vertex(currentLine[i]),
Integer.parseInt(currentLine[ i]));
}
}
when you do:
g.addEdge(vertex, new Vertex(currentLine[i]), Integer.parseInt(currentLine[ i]));
here you create a new vertex with the name currentLine[i] even if there's already one with the same name in the graph, it'll create a new one and will not magically reuse the existing one.
To remedy this problem, add a function in your Graph class for example to get an existing vertex by name or create one if it's not found.
In your Graph class add the following method:
public Vertex getOrCreateVertex(String name) {
for (Vertex v : nodes) {
if (v.name.equals(name)) {
return v;
}
}
Vertex newVertex = new Vertex(name);
nodes.add(newVertex);
return newVertex;
}
And change the part reading the file as follows:
while (file.hasNext()) {
String[] currentLine = file.nextLine().split(" |,");
Vertex vertex = g.getOrCreateVertex(currentLine[0]);
// set the graph's source vertex
if (vertex.getName().equals(sourceID)) {
g.source = vertex;
}
// read current line for adjacent vertices and their edge weights
for (int i = 1; i < currentLine.length; i ) {
g.addEdge(vertex, g.getOrCreateVertex(currentLine[i]),
Integer.parseInt(currentLine[ i]));
}
}