Sunday, November 29, 2015

Single source shortest paths using Topological Sort

This program finds the shortest paths to all vertices from a given source vertex.
 
The algorithm is based on first topologically sorting the vertices and then using
the topological order for relaxing edges connected to the current vertex in the order
until the last vertex is done. The result is the shortest distances from the source
vertex to all other vertices.

Source:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;
 
//Directed + Weighted

class DWEdge{
    int from, to;
    double weight;
    
    DWEdge(int from, int to, double weight){
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
}

class TopologicalSorter {
    
    private int E, V;
    private ArrayList<ArrayList<DWEdge>> al;
    private boolean marked[];
    private Stack<Integer> stack;
    
    TopologicalSorter(int V){
        this.V = V; 
        marked = new boolean[V];
        stack = new Stack<>(); 
    }
    
    
    public void dfs(int vertex){ 
        if(!marked[vertex]){
            marked[vertex] = true;
            for(DWEdge e:al.get(vertex)){
                int v = e.to;
                dfs(v);
            }
            stack.push(vertex);
        }
    }
    
    
    
    public static Stack<Integer> sort(ArrayList<ArrayList<DWEdge>> graph){
        TopologicalSorter ts = new TopologicalSorter(graph.size());
        ts.al = graph;
        for(int i=0;i<ts.V;++i) ts.dfs(i);
        
        return ts.stack;
    } 
}

public class SSSPTopologicalOrder {
    
    private ArrayList<ArrayList<DWEdge>> graph;
    private int edgeTo[];
    private double distTo[];
    private int V;
    
    SSSPTopologicalOrder(int V){
        graph = new ArrayList<>();
        graph.ensureCapacity(V);
        for(int i=0;i<V;++i)graph.add(new ArrayList<>());
        edgeTo = new int[V];
        distTo = new double[V];
        this.V = V;
    }
    
    public void addEdge(int from, int to, double weight){
        graph.get(from).add(new DWEdge(from, to, weight));
    }
    
    public void findShortestPaths(int s){  
        
        Arrays.fill(distTo, Double.POSITIVE_INFINITY);
        distTo[s] = 0; 
        
        Stack<Integer> sortedVertices = TopologicalSorter.sort(graph);
        
        while(!sortedVertices.isEmpty()){
            int v = sortedVertices.pop(); 
            for(DWEdge e : graph.get(v)){
               relax(e);
            }
        }
    }
    
    
    public void relax(DWEdge e){ 
        if(distTo[e.to] > distTo[e.from] + e.weight){
            distTo[e.to] = distTo[e.from] + e.weight;
            edgeTo[e.to] = e.from; 
        }
    }
    
    public static void main(String[] args){
        
        double startTime = System.nanoTime();
        SSSPTopologicalOrder d = new SSSPTopologicalOrder(8);
        
        d.addEdge(0,1,5);   d.addEdge(3,6,9);   
        d.addEdge(0,4,9);   d.addEdge(4,5,4);
        d.addEdge(0,7,8);   d.addEdge(4,6,20);
        d.addEdge(1,2,12);  d.addEdge(4,7,5);
        d.addEdge(1,3,15);  d.addEdge(5,2,1);
        d.addEdge(1,7,4);   d.addEdge(5,6,13);
        d.addEdge(2,3,3);   d.addEdge(7,5,6);
        d.addEdge(2,6,11);  d.addEdge(7,2,7);
        
        d.findShortestPaths(0);
        
        double endTime = System.nanoTime();
        
        System.out.println("Results: ");
        for(int i=0;i<d.V;++i){
            System.out.println("Vertex "+i+" edgeTo["+i+"] = "+d.edgeTo[i]+" distTo["+i+"] = "+d.distTo[i]);
        }
        
        System.out.println("\nTime Taken : "+(endTime-startTime)/10E9+"s");
        
    }
}

Output:

Results:
Vertex 0 edgeTo[0] = 0 distTo[0] = 0.0
Vertex 1 edgeTo[1] = 0 distTo[1] = 5.0
Vertex 2 edgeTo[2] = 5 distTo[2] = 14.0
Vertex 3 edgeTo[3] = 2 distTo[3] = 17.0
Vertex 4 edgeTo[4] = 0 distTo[4] = 9.0
Vertex 5 edgeTo[5] = 4 distTo[5] = 13.0
Vertex 6 edgeTo[6] = 2 distTo[6] = 25.0
Vertex 7 edgeTo[7] = 0 distTo[7] = 8.0

Time Taken : 8.9406E-5s

No comments:

Post a Comment