Graphs II: Directed Graphs & Advanced Algorithms

Directed Graphs & Representations

Dijkstra's Shortest Path Algorithm

Topological Sorting

Java Implementation

import java.util.*;

public class DijkstraAlgorithm {
    static class Edge {
        int destination;
        int weight;
        
        Edge(int destination, int weight) {
            this.destination = destination;
            this.weight = weight;
        }
    }
    
    static class Graph {
        private int V; // Number of vertices
        private List> adjList;
        
        public Graph(int V) {
            this.V = V;
            adjList = new ArrayList<>(V);
            for (int i = 0; i < V; i++) {
                adjList.add(new ArrayList<>());
            }
        }
        
        public void addEdge(int source, int destination, int weight) {
            adjList.get(source).add(new Edge(destination, weight));
        }
        
        public int[] dijkstra(int source) {
            // Create a min heap to store vertices and their distances
            PriorityQueue minHeap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
            
            // Initialize distances array
            int[] distance = new int[V];
            Arrays.fill(distance, Integer.MAX_VALUE);
            distance[source] = 0;
            
            // Add source to min heap
            minHeap.add(new int[]{source, 0});
            
            while (!minHeap.isEmpty()) {
                int[] current = minHeap.poll();
                int u = current[0]; // Current vertex
                int dist = current[1]; // Distance from source to u
                
                // If current distance is greater than the calculated one, skip
                if (dist > distance[u]) continue;
                
                // Check all neighbors of u
                for (Edge edge : adjList.get(u)) {
                    int v = edge.destination;
                    int weight = edge.weight;
                    
                    // If there is a shorter path to v through u
                    if (distance[u] != Integer.MAX_VALUE && 
                        distance[u] + weight < distance[v]) {
                        // Update distance of v
                        distance[v] = distance[u] + weight;
                        minHeap.add(new int[]{v, distance[v]});
                    }
                }
            }
            
            return distance;
        }
    }
    
    // Driver code to test the implementation
    public static void main(String[] args) {
        int V = 5;
        Graph graph = new Graph(V);
        
        // Add edges (source, destination, weight)
        graph.addEdge(0, 1, 4);
        graph.addEdge(0, 2, 1);
        graph.addEdge(1, 3, 1);
        graph.addEdge(2, 1, 2);
        graph.addEdge(2, 3, 5);
        graph.addEdge(3, 4, 3);
        
        // Calculate shortest paths from source 0
        int[] distances = graph.dijkstra(0);
        
        // Print the result
        System.out.println("Shortest distances from source 0:");
        for (int i = 0; i < V; i++) {
            System.out.println("To vertex " + i + ": " + distances[i]);
        }
    }
}

Java Implementation

import java.util.*;

public class TopologicalSort {
    static class Graph {
        private int V; // Number of vertices
        private List> adjList;
        
        public Graph(int V) {
            this.V = V;
            adjList = new ArrayList<>(V);
            for (int i = 0; i < V; i++) {
                adjList.add(new ArrayList<>());
            }
        }
        
        public void addEdge(int source, int destination) {
            adjList.get(source).add(destination);
        }
        
        // Topological Sort using DFS
        public List topologicalSort() {
            Stack stack = new Stack<>();
            boolean[] visited = new boolean[V];
            
            // Call recursive helper function for all vertices
            for (int i = 0; i < V; i++) {
                if (!visited[i]) {
                    topologicalSortUtil(i, visited, stack);
                }
            }
            
            // Create result list from stack
            List result = new ArrayList<>();
            while (!stack.isEmpty()) {
                result.add(stack.pop());
            }
            
            return result;
        }
        
        private void topologicalSortUtil(int v, boolean[] visited, Stack stack) {
            // Mark the current node as visited
            visited[v] = true;
            
            // Recur for all adjacent vertices
            for (Integer neighbor : adjList.get(v)) {
                if (!visited[neighbor]) {
                    topologicalSortUtil(neighbor, visited, stack);
                }
            }
            
            // Push current vertex to stack after all neighbors are visited
            stack.push(v);
        }
    }
    
    // Driver code to test the implementation
    public static void main(String[] args) {
        int V = 6;
        Graph graph = new Graph(V);
        
        // Add edges for a DAG representing course prerequisites
        graph.addEdge(5, 2);
        graph.addEdge(5, 0);
        graph.addEdge(4, 0);
        graph.addEdge(4, 1);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);
        
        // Perform topological sort
        List result = graph.topologicalSort();
        
        // Print the result
        System.out.println("Topological Sort Order:");
        for (Integer vertex : result) {
            System.out.print(vertex + " ");
        }
    }
}

Guided Practice

For additional hands-on practice and in-depth exercises on directed graphs and graph algorithms, check out our comprehensive guided project:

• Guided Project: Directed Graphs