Finding the shortest path in a graph

Question

Could you please advise on the code and its design? Is there any way I can apply object oriented principles to make the design robust yet flexible?

public class RouteFinder{
 /** Used to compute shortest distance from source station to all other station in a given network.
 * @param source source station from which shortest distance will be calculated to the stations
 */
 public 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);
 }
 }
 }
 }
 /** Used to return the shortest path from a source to destination station.
 * @param target destination station
 * @return shortest path from source station to destination station.
 */
 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;
 }
}

• tim: is this your complete code? computePaths doesn't return a path, and also doesn't seem to create a path for source. Also, it's unclear how computePaths and getShortestPathTo relate to each other. Do you have an example usage?

Answer 1

You mentioned OOP, and thats great, and OOP is all about code reusability and extensibility,and this code is a good example of a Candy Machine Interface. And that is, users of this class might do mistakes while using it. users could call the static the method getShortestPathTo before calling instance method computePaths and this would lead to wrong routes because weights weren't computed properly. You should try your best to force right behavior.

class RouteFinder{
 
 RouteFinder(Vertex source){
 computePaths(source);
 }
 private computePaths(Vertex source){
 //It is private,users dont need to know about this
 }
 public List<Vertex> getShortestPathTo(Vertex target){
 //..
 }
}

As you can see here no static methods anymore, static usually presents a global behavior, and I need to force users to go through the constructor so I make sure weights are computed properly. I suppose that what you using is Dijkstra algorithm (not sure though), where your class name is RouteFinder, that's a bit misleading because Dijkstra is not the only algorithm and it doesn't work with negative weights, and you need something like Bellman-Ford for that.If you don't want to support negative weights for now, it is fine, but you should be able to add this functionality in the future.And this leads for extracting the Route finder to an interface

 interface RouteFinder{
 List<Vertex> shortestPath(Vertex target);
 } 
 class Dijkstra implements RouteFinder{
 ...
 }
 
 class BellmanFord implements RouteFinder{
 ...
 }

And it would be great if you just expose the interface and keep concrete implementation with package access, a good API is a compact one. And for that you can have a static factory to get the right implementation

public static RouteFinder getInstance(Vertex source){
 if(hasNegativeWeight){ 
 return new BelmmanFord(source); 
 }else{
 return new Dijkstra(source);
 }
}

One more thing, is it possible to have duplicated vertices on the same graph? I dont think so, and hence getShortestPathTo should return a Set of vertices rather than a List

• Prasanna Aarthi: A very comprehensive answer.Thank you so much, I will definitely refactor my code.
• Rob Audenaerde: Although a Set can be seen as correct, an ordering is somewhat implied by a path; so I'd prefer some ordered/navigatable result.