1. Introduction

In this tutorial, we’ll discuss about finding the shortest path with topological ordering. Usually we use Dijkstra’s algorithm if we want to find the shortest path in an arbitrary graph G(V,E) graph.

But if the graph is a directed acyclic graph, we can achieve linear running time to calculate the shortest path in a G(V,E) directed acyclic graph. We can find the shortest path in a directed acyclic graph (DAG) with topological ordering in O(V+E) linear running time. It only works when a valid topological order exists.

2. Pseudocode

Following is the pseudocode:

function shortestPathDAG(graph, start):
    # Step 1: Perform topological sort
    topoOrder = topologicalSort(graph)

    # Step 2: Initialize distances
    distance = [∞] * number_of_vertices
    distance[start] = 0

    # Step 3: Relax edges in topological order
    for vertex in topoOrder:
        for (neighbor, weight) in graph[vertex]:
            distance[neighbor] = min(distance[neighbor], distance[vertex] + weight)

    return distance

In the following figure S is the source vertex which is the starting point. We calculate the shortest path to every other vertex starting with the s vertex. If we find a shorter path to the vertex v via u vertex then we have to check if distance[u] + w < distance[v] which means we have found a shorter path.

3. Implementation

Now, we’ll find the shortest path of the following graph:

Vertex.java

import java.util.ArrayList;
import java.util.List;

public class Vertex {
    private String name;
    private boolean visited;
    //shortest path from the source vertex to actual vertex
    private int minDistance;
    //the previous node in the shortest path
    private Vertex predecessor;
    private List<Edge> adjacencyList;

    public Vertex(String name){
        this.name=name;
        this.minDistance = Integer.MAX_VALUE;
        this.adjacencyList = new ArrayList<>();
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public boolean isVisited() {
        return visited;
    }

    public void setVisited(boolean visited) {
        this.visited = visited;
    }

    public int getMinDistance() {
        return minDistance;
    }

    public void setMinDistance(int minDistance) {
        this.minDistance = minDistance;
    }

    public Vertex getPredecessor() {
        return predecessor;
    }

    public void setPredecessor(Vertex predecessor) {
        this.predecessor = predecessor;
    }

    public List<Edge> getNeighbors() {
        return adjacencyList;
    }

    public void addNeighbor(Edge edge) {
        this.adjacencyList.add(edge);
    }

    @Override
    public String toString() {
        return "Vertex{" +
                "name='" + name + '\'' +
                ", predecessor=" + predecessor +
                '}';
    }
}

Edge.java

public class Edge {
    private Vertex target;
    private int weight;

    public Edge(Vertex target, int weight){
        this.target = target;
        this.weight = weight;
    }

    public Vertex getTarget() {
        return target;
    }

    public int getWeight() {
        return weight;
    }
}

TopologicalOrdering.java

import java.util.Stack;
import java.util.List;

public class TopologicalOrdering {

    private Stack<Vertex> stack;

    public TopologicalOrdering(List<Vertex> graph){
        this.stack = new Stack<>();
        for(int i=0; i<graph.size(); i++){
            if(!graph.get(i).isVisited()){
                dfs(graph.get(i));
            }
        }
    }

    public void dfs(Vertex vertex){
        vertex.setVisited(true);

        //for all the neighbors of a vertex
        for(Edge e: vertex.getNeighbors()){
            if(!e.getTarget().isVisited()){
                dfs(e.getTarget());
            }
        }
        stack.push(vertex);
    }

    public Stack<Vertex> getStack(){
        return this.stack;
    }
}

ShortestPath.java

import java.util.List;
import java.util.Stack;

public class ShortestPath {

    private TopologicalOrdering topologicalOrdering;

    public ShortestPath(List<Vertex> graph){
        this.topologicalOrdering = new TopologicalOrdering(graph);
        graph.get(0).setMinDistance(0);
    }

    public void compute(){
        Stack<Vertex> topologicalOrder = topologicalOrdering.getStack();
        while(!topologicalOrder.isEmpty()){
            Vertex u = topologicalOrder.pop();
            if(u.getMinDistance() == Integer.MAX_VALUE) continue;
            for(Edge e: u.getNeighbors()){
                Vertex v = e.getTarget();
                if(v.getMinDistance() > u.getMinDistance() + e.getWeight()){
                    v.setMinDistance(u.getMinDistance()+e.getWeight());
                    v.setPredecessor(u);
                }
            }
        }
    }
}

App.java

import java.util.List;
import java.util.ArrayList;
import java.util.Stack;

public class App {
    public static void main(String args[]){
        List<Vertex> graph = new ArrayList();

        Vertex v0 = new Vertex("S");
        Vertex v1 = new Vertex("A");
        Vertex v2 = new Vertex("B");
        Vertex v3 = new Vertex("C");
        Vertex v4 = new Vertex("D");
        Vertex v5 = new Vertex("E");

        v0.addNeighbor(new Edge(v1, 1));
        v0.addNeighbor(new Edge(v3, 2));
        v1.addNeighbor(new Edge(v2, 6));
        v2.addNeighbor(new Edge(v4, 1));
        v2.addNeighbor(new Edge(v5, 2));
        v3.addNeighbor(new Edge(v1, 4));
        v3.addNeighbor(new Edge(v4, 3));
        v4.addNeighbor(new Edge(v5, 1));

        graph.add(v0);
        graph.add(v1);
        graph.add(v2);
        graph.add(v3);
        graph.add(v4);
        graph.add(v5);

        ShortestPath algorithm = new ShortestPath(graph);
        algorithm.compute();

        for(Vertex v: graph){
            System.out.println("Distance from s: " + v.getMinDistance() + " - " + v.getPredecessor());
        }
    }
}

Output

Distance from s: 0 - null
Distance from s: 1 - Vertex{name='S', predecessor=null}
Distance from s: 7 - Vertex{name='A', predecessor=Vertex{name='S', predecessor=null}}
Distance from s: 2 - Vertex{name='S', predecessor=null}
Distance from s: 5 - Vertex{name='C', predecessor=Vertex{name='S', predecessor=null}}
Distance from s: 6 - Vertex{name='D', predecessor=Vertex{name='C', predecessor=Vertex{name='S', predecessor=null}}}