Graphs II: Advanced Concepts

Shortest Path Algorithms

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights.

public class WeightedGraph {
    private Map> adjacencyList;
    
    private class Edge {
        String destination;
        int weight;
        
        public Edge(String destination, int weight) {
            this.destination = destination;
            this.weight = weight;
        }
    }
    
    // ... Constructor and basic methods ...
    
    public Map dijkstra(String start) {
        // Track distances from start to each vertex
        Map distances = new HashMap<>();
        
        // Priority queue to select the vertex with min distance
        PriorityQueue queue = new PriorityQueue<>(
            Comparator.comparingInt(node -> node.distance)
        );
        
        // Initialize distances
        for (String vertex : adjacencyList.keySet()) {
            if (vertex.equals(start)) {
                distances.put(vertex, 0);
            } else {
                distances.put(vertex, Integer.MAX_VALUE);
            }
        }
        
        // Add start vertex to the queue
        queue.add(new Node(start, 0));
        
        // Process all vertices
        while (!queue.isEmpty()) {
            Node current = queue.poll();
            String currentVertex = current.vertex;
            int currentDistance = current.distance;
            
            // Skip if we've already found a better path
            if (currentDistance > distances.get(currentVertex)) {
                continue;
            }
            
            // Process all neighbors
            for (Edge edge : adjacencyList.get(currentVertex)) {
                String neighbor = edge.destination;
                int weight = edge.weight;
                int distance = currentDistance + weight;
                
                // If we found a better path, update and enqueue
                if (distance < distances.get(neighbor)) {
                    distances.put(neighbor, distance);
                    queue.add(new Node(neighbor, distance));
                }
            }
        }
        
        return distances;
    }
    
    // Helper class for priority queue
    private class Node {
        String vertex;
        int distance;
        
        public Node(String vertex, int distance) {
            this.vertex = vertex;
            this.distance = distance;
        }
    }
}

Visual Example: Dijkstra's Algorithm

Consider this weighted graph (numbers on edges represent weights):

    A --- 2 --- B
    |           |
    4           3
    |           |
    C --- 1 --- D

Steps to find shortest paths from A:

1. Initialize distances: A=0, B=∞, C=∞, D=∞
2. Process A, update neighbors: B=2, C=4
3. Process B (nearest to A), update neighbors: D=5 (via B)
4. Process C, update neighbors: D=5 (already found via B)
5. Process D, no updates needed

Final distances from A: B=2, C=4, D=5

Implementation Steps

1. 1

   Implement Dijkstra's Algorithm

   Create a shortest path finder using priority queues

   Key components:

   • Distance map to track shortest known distance to each vertex
   • Priority queue to process vertices in order of current shortest distance
   • Edge relaxation - constantly update distances when shorter paths are found
2. 2

   Build Minimum Spanning Tree

   Implement Prim's algorithm for finding a minimum spanning tree

   public Set primMST(String start) {
       Set mst = new HashSet<>();
       Set visited = new HashSet<>();
       
       // Priority queue to select minimum weight edge
       PriorityQueue pq = new PriorityQueue<>(
           Comparator.comparingInt(edge -> edge.weight)
       );
       
       // Start with the given vertex
       visited.add(start);
       
       // Add all edges from start vertex
       for (Edge edge : adjacencyList.get(start)) {
           pq.add(edge);
       }
       
       // Process until all vertices are visited or queue is empty
       while (!pq.isEmpty() && visited.size() < adjacencyList.size()) {
           Edge minEdge = pq.poll();
           
           // Skip if destination already visited
           if (visited.contains(minEdge.destination)) {
               continue;
           }
           
           // Add to MST and mark as visited
           mst.add(minEdge);
           visited.add(minEdge.destination);
           
           // Add all edges from the new vertex
           for (Edge edge : adjacencyList.get(minEdge.destination)) {
               if (!visited.contains(edge.destination)) {
                   pq.add(edge);
               }
           }
       }
       
       return mst;
   }

3. 3

   Optimize Performance

   Improve algorithm efficiency using appropriate data structures

   • Use indexed priority queues for faster decrease-key operations
   • Early stopping when possible
   • Path reconstruction using a predecessor map

   // Add predecessor tracking to Dijkstra's algorithm
   public Map findShortestPathPredecessors(String start) {
       Map distances = new HashMap<>();
       Map predecessors = new HashMap<>();
       
       // ... similar to regular Dijkstra's ...
       
       // When updating distances, also update predecessors
       if (distance < distances.get(neighbor)) {
           distances.put(neighbor, distance);
           predecessors.put(neighbor, currentVertex); // Track path
           queue.add(new Node(neighbor, distance));
       }
       
       return predecessors;
   }
   
   // Reconstruct the shortest path from predecessors
   public List reconstructPath(String start, String end, Map predecessors) {
       List path = new ArrayList<>();
       
       // Start from the end and work backwards
       for (String at = end; at != null; at = predecessors.get(at)) {
           path.add(at);
       }
       
       // Reverse to get start-to-end path
       Collections.reverse(path);
       
       // Check if there is a valid path
       if (path.get(0).equals(start)) {
           return path;
       } else {
           return Collections.emptyList(); // No path exists
       }
   }

Bellman-Ford Algorithm: Handling Negative Weights

Unlike Dijkstra's, the Bellman-Ford algorithm can handle graphs with negative edge weights, as long as there are no negative cycles.

public Map bellmanFord(String start) {
    Map distances = new HashMap<>();
    List allEdges = new ArrayList<>();
    
    // Initialize distances
    for (String vertex : adjacencyList.keySet()) {
        distances.put(vertex, Integer.MAX_VALUE);
    }
    distances.put(start, 0);
    
    // Collect all edges
    for (String source : adjacencyList.keySet()) {
        for (Edge edge : adjacencyList.get(source)) {
            allEdges.add(new Edge(source, edge.destination, edge.weight));
        }
    }
    
    // Relax all edges |V| - 1 times
    int vertexCount = adjacencyList.size();
    for (int i = 0; i < vertexCount - 1; i++) {
        for (Edge edge : allEdges) {
            String source = edge.source;
            String dest = edge.destination;
            int weight = edge.weight;
            
            if (distances.get(source) != Integer.MAX_VALUE && 
                distances.get(source) + weight < distances.get(dest)) {
                distances.put(dest, distances.get(source) + weight);
            }
        }
    }
    
    // Check for negative cycles
    for (Edge edge : allEdges) {
        String source = edge.source;
        String dest = edge.destination;
        int weight = edge.weight;
        
        if (distances.get(source) != Integer.MAX_VALUE && 
            distances.get(source) + weight < distances.get(dest)) {
            System.out.println("Graph contains a negative weight cycle");
            return new HashMap<>(); // Return empty if negative cycle
        }
    }
    
    return distances;
}

Comparison of Graph Algorithms

Exercise 1: Shortest Path

Implement Dijkstra's algorithm to find the shortest path between two vertices in a weighted graph.

public List findShortestPath(String start, String end) {
    // Step 1: Run Dijkstra's to get distances and predecessors
    Map distances = new HashMap<>();
    Map predecessors = new HashMap<>();
    
    // ... your Dijkstra's implementation here ...
    
    // Step 2: Reconstruct the path from start to end
    List path = new ArrayList<>();
    
    // ... path reconstruction logic here ...
    
    return path;
}

Hint: Remember to track predecessor vertices during Dijkstra's so you can reconstruct the full path.

Exercise 2: Minimum Spanning Tree

Implement Prim's algorithm to find the minimum spanning tree of a weighted graph.

public Set findMinimumSpanningTree() {
    // Your implementation here
    // Remember to use a priority queue to select minimum-weight edges
}

Hint: Start from any vertex, grow the MST by always adding the minimum-weight edge that connects a visited vertex to an unvisited one.

Exercise 3: Negative Cycle Detection

Implement a modified Bellman-Ford algorithm to detect negative cycles in a graph.

public boolean hasNegativeCycle() {
    // Your implementation here
    // Hint: After |V|-1 iterations of Bellman-Ford, any further
    // distance improvements indicate a negative cycle
}

Exercise 4: Multi-Source Shortest Path

Implement the Floyd-Warshall algorithm to find shortest paths between all pairs of vertices.

public int[][] floydWarshall() {
    // Your implementation here
    // Hint: Use a distance matrix and consider all vertices as intermediates
}

Exercise 5: Maximum Flow

Implement the Ford-Fulkerson algorithm to find the maximum flow in a network from a source to a sink.

public int findMaxFlow(String source, String sink) {
    // Your implementation here
    // Hint: Repeatedly find augmenting paths and update residual capacities
}

Exercise 6: Advanced - Traveling Salesman Problem

Implement a solution to the Traveling Salesman Problem using dynamic programming.

public List solveTSP() {
    // Your implementation here
    // Hint: Use bit manipulation to represent visited sets efficiently
}

Note: This is an NP-hard problem, so exact solutions are exponential. For large graphs, consider using approximation algorithms instead.