Dijkstras Algorithm

[Thomas Nilsen]

I came across an interesting programming challenge, which I'm trying to solve.

In my mind Dijkstras algorithm is the best solution, since what they're essentially asking is to find the shortest path in a un-directed graph.

Here is my solution, but I don't get the correct answer, so I'd like some feedback on my code. Maybe my mistake is obvious.

Any help on the would truly be appreciated!

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

class Solution {
	public static void main(String[] args) {
		
        //Read first line of input
		Scanner s = new Scanner(System.in);
		String[] constants = s.nextLine().split(" ");
		
        //CONSTANTS
		final int N = Integer.parseInt(constants[0]);
		final int H = Integer.parseInt(constants[1]);
		final int V = Integer.parseInt(constants[2]);
        
        //Datastructures
        List<Coordinate> junctions = new ArrayList<>();
        List<Coordinate> paths = new ArrayList<>();
        List<Vertex> vertices = new ArrayList<>();
        
        //Read N junctions
        for(int i = 0; i < N; i++) {
            junctions.add(Coordinate.readInput(s));
        }
        
        // Read N-1 paths between junctions
        for(int i = 0; i < N-1; i++) {
            paths.add(Coordinate.readInput(s));
        }
        
        for(int i = 0; i < N; i++){
            vertices.add(new Vertex(i+1, junctions.get(i)));
        }

        for(int i = 0; i < N - 1; i++){
            int x = junctions.get(paths.get(i).getX() - 1).getX();
            int x1 = junctions.get(paths.get(i).getY() - 1).getX();
            int y = junctions.get(paths.get(i).getX() - 1).getY();
            int y1 = junctions.get(paths.get(i).getY() - 1).getY();
            
            Vertex vertex1 = vertices.get(paths.get(i).getX() - 1);
            Vertex vertex2 = vertices.get(paths.get(i).getY() - 1);
            
            double distance = Math.sqrt(Math.pow(x - x1, 2) + Math.pow(y - y1, 2));

            vertex1.addNeighbour(new Edge(distance, vertex2));
            vertex2.addNeighbour(new Edge(distance, vertex1));
        }

        int h = 0;
        int v = 0;
        int unorderedPairs = 0;
        
        Algorithm a = new Algorithm();
        
        for(int i = 0; i < N-1; i++) {
            a.shortestPath(vertices.get(paths.get(i).getX()-1));
            
            for(Vertex vertex : a.getShortestPathTo(vertices.get(paths.get(i).getY()-1))) {
                h += Math.abs(h - vertex.getPoint().getX());
                v += Math.abs(v - vertex.getPoint().getY());
            }
            if (h > H || v > V) {
                unorderedPairs++;
                h = v = 0;
            }
            
            for(Vertex vtx : a.getShortestPathTo(vertices.get(paths.get(i).getY()-1))){
                vtx.setMinDistance(0);
                vtx.setPreviousVertex(null);  
            }
            
        }
        System.out.println(unorderedPairs);
    }
}

class Vertex implements Comparable<Vertex> {
	private int id;
	private List<Edge> adjacencyList;
	private Vertex previousVertex;
	private double minDistance = Double.POSITIVE_INFINITY;
    private Coordinate point;
	
	public Vertex(int id, Coordinate point) {
		this.id = id;
        this.point = point;
		this.adjacencyList = new ArrayList<>();
    }
    
    public int getID() {
        return this.id;
    }
    
    public Coordinate getPoint() {
        return this.point;
    }
	
	public List<Edge> getAdjacencyList() {
		return this.adjacencyList;
	}
	
	public void addNeighbour(Edge edge) {
		this.adjacencyList.add(edge);
	}
	
	public Vertex getPreviousVertex() {
		return this.previousVertex;
	}
	
	public void setPreviousVertex(Vertex previousVertex) {
		this.previousVertex = previousVertex;
	}
	
	public double getMinDistance() {
		return this.minDistance;
	}
	
	public void setMinDistance(double minDistance) {
		this.minDistance = minDistance;
	}
    
    public int compareTo(Vertex other) {
        return Double.compare(this.minDistance, other.minDistance);
    }
}


class Edge {
	private double weight;
	private Vertex targetVertex;
	
	public Edge(double weight, Vertex targetVertex) {
		this.weight = weight;
		this.targetVertex = targetVertex;
	}
	
	public double getWeight() {
		return this.weight;
	}
	
	public void setWeight(double weight) {
		this.weight = weight;
	}
	
	public Vertex getTargetVertex() {
		return this.targetVertex;
	}
		
	public void setTargetVertex(Vertex targetVertex) {
		this.targetVertex = targetVertex;
	}
}

class Algorithm {
	public void shortestPath(Vertex startVertex) {
		startVertex.setMinDistance(0);
		PriorityQueue<Vertex> queue = new PriorityQueue<>();
		queue.add(startVertex);
		
		while (!queue.isEmpty()) {
			Vertex actualVertex = queue.poll();
			
			for (Edge edge : actualVertex.getAdjacencyList()) {
				Vertex v = edge.getTargetVertex();
				double weight = edge.getWeight();				
                double currentDistance = actualVertex.getMinDistance() + weight;
				
				if (currentDistance < v.getMinDistance()) {
					queue.remove(v);
					v.setMinDistance(currentDistance);
					v.setPreviousVertex(actualVertex);
					queue.add(v);
				}
			}
		}
	}
	
	public List<Vertex> getShortestPathTo(Vertex targetVertex){
		List<Vertex> path = new ArrayList<>();
        for (Vertex vertex = targetVertex; vertex != null; vertex = vertex.getPreviousVertex()){
            path.add(vertex);
        }
        Collections.reverse(path);
        return path;	
	}
}

class Coordinate {
    private int x;
    private int y;
    
    Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
    
    public int getX() {
        return this.x;
    } 
    
    public int getY() {
        return this.y;
    }

    public static Coordinate readInput(Scanner in) {
       String[] temp = in.nextLine().split(" ");
       return new Coordinate(Integer.parseInt(temp[0]), Integer.parseInt(temp[1]));
    }
}

[Stefan Evans]

Feedback on code: It is fairly hard to read.
Some more comments and better variable names might help a little.

I could follow the reading in of input. The Junctions and Paths are explained in the problem definition. What are "vertices" ?
But then I got lost at line 42 when you are in loop doing calculations:

int x = junctions.get(paths.get(i).getX() - 1).getX();

That line looks funny to me.
Getting a junction by index based on the x value of a path!?!?
What is this loop trying to accomplish?
What do the x,y, x1,y1 represent?

Suggestions for debugging:
Add logging statements at various points to check what is happening in your internal program.

This bit also looks wrong to me.

            for(Vertex vertex : a.getShortestPathTo(vertices.get(paths.get(i).getY()-1))) {
            	System.out.println("h,v = " + h + "," + v);
                h += Math.abs(h - vertex.getPoint().getX());
                v += Math.abs(v - vertex.getPoint().getY());
            }

I assume "h" and "v" are the total distance travelled horizontally and vertically within the path.
I am pretty sure you should not be using h and v (distance travelled so far) in the Math.abs calculation. You should be looking at current and previous junctions to determine how much to add to h and v travelled to date.

Also rather than typing in the numbers each time, try the following:

String inputString = "3 2 1\r\n" + 
    			"0 0\r\n" + 
    			"1 1\r\n" + 
    			"2 0\r\n" + 
    			"1 2\r\n" + 
    			"2 3";
    	
        Scanner s = new Scanner(inputString);

It saves MASSIVE amounts of time running it if you don't have to type in the details again each time.
You should try refactoring your code to allow that a bit easier.

[Junilu Lacar]

As far as readability, I didn't find it too bad. Some variable names could be more explicit to differentiate them from others. For example, some parts use v to refer to a vertex while other parts use v to refer to a vertical distance. Having to differentiate between h and H also adds to the conceptual weight. The static method readInput in the Coordinate class is really a static factory method so it's better to name it something like newCoordinateFrom or something like that. Names are better when they reveal the logical intent rather than the technical details.

I referred to the problem that you linked to and you seem to have pretty much followed the names used there but it's still a bit of a bother to flip back and forth to see what some variables are supposed to represent.

It would help if you told us which particular variation of the algorithm you are trying to implement just so we are on the same page. If you have some pseudo code that you based your implementation, please share it.

Also, from the problem:

Now he has thoughts about returning the vehicle back to the seller. But he first wants to know, if it's even worth it. That's why he wants to know the number of unordered pairs (i,j) such that it is not possible to drive a customer from junction i to junction j.

Are you sure your results represent these or are you getting the shortest paths? Because I don't think you're actually looking for the shortest paths as the solution here. I don't know, I could be wrong but that's what it seems to me after a cursory read.