Shortest Path Algorithms

import java.util.*;
 
public class Dijkstra {
    static class Edge {
        int to, weight;
        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }
    
    private List<Edge>[] adj;
    private int V;
    
    public Dijkstra(int V) {
        this.V = V;
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }
    
    public void addEdge(int u, int v, int weight) {
        adj[u].add(new Edge(v, weight));
        adj[v].add(new Edge(u, weight));
    }
    
    // Dijkstra's algorithm
    public int[] dijkstra(int source) {
        int[] distance = new int[V];
        boolean[] visited = new boolean[V];
        
        // Initialize distances
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[source] = 0;
        
        // Use priority queue for efficiency
        PriorityQueue<Integer> pq = new PriorityQueue<>(
            (u, v) -> Integer.compare(distance[u], distance[v])
        );
        pq.add(source);
        
        while (!pq.isEmpty()) {
            int u = pq.poll();
            
            if (visited[u]) continue;
            visited[u] = true;
            
            // Relax edges
            for (Edge edge : adj[u]) {
                int v = edge.to;
                int weight = edge.weight;
                
                if (distance[u] + weight < distance[v]) {
                    distance[v] = distance[u] + weight;
                    pq.add(v);
                }
            }
        }
        
        return distance;
    }
    
    public static void main(String[] args) {
        Dijkstra g = new Dijkstra(5);
        g.addEdge(0, 1, 4);
        g.addEdge(0, 2, 2);
        g.addEdge(1, 2, 1);
        g.addEdge(1, 3, 5);
        g.addEdge(2, 3, 8);
        g.addEdge(2, 4, 10);
        g.addEdge(3, 4, 2);
        
        int[] distances = g.dijkstra(0);
        System.out.println("Shortest distances from 0:");
        for (int i = 0; i < distances.length; i++) {
            System.out.println("  to " + i + ": " + distances[i]);
        }
    }
}

public class BellmanFord {
    static class Edge {
        int u, v, weight;
        Edge(int u, int v, int weight) {
            this.u = u;
            this.v = v;
            this.weight = weight;
        }
    }
    
    private List<Edge> edges;
    private int V, E;
    
    public BellmanFord(int V) {
        this.V = V;
        edges = new ArrayList<>();
    }
    
    public void addEdge(int u, int v, int weight) {
        edges.add(new Edge(u, v, weight));
    }
    
    // Bellman-Ford algorithm
    public int[] bellmanFord(int source) {
        int[] distance = new int[V];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[source] = 0;
        
        // Relax edges V-1 times
        for (int i = 0; i < V - 1; i++) {
            for (Edge edge : edges) {
                if (distance[edge.u] != Integer.MAX_VALUE &&
                    distance[edge.u] + edge.weight < distance[edge.v]) {
                    distance[edge.v] = distance[edge.u] + edge.weight;
                }
            }
        }
        
        // Check for negative cycles
        for (Edge edge : edges) {
            if (distance[edge.u] != Integer.MAX_VALUE &&
                distance[edge.u] + edge.weight < distance[edge.v]) {
                System.out.println("Negative cycle detected!");
                return null;
            }
        }
        
        return distance;
    }
    
    public static void main(String[] args) {
        BellmanFord g = new BellmanFord(5);
        g.addEdge(0, 1, 4);
        g.addEdge(0, 2, 2);
        g.addEdge(1, 2, -3);  // Negative edge
        g.addEdge(1, 3, 5);
        g.addEdge(2, 3, 8);
        
        int[] distances = g.bellmanFord(0);
        if (distances != null) {
            System.out.println("Shortest distances: " + Arrays.toString(distances));
        }
    }
}

public class FloydWarshall {
    private static final int INF = Integer.MAX_VALUE / 2;
    
    private int[][] dist;
    private int V;
    
    public FloydWarshall(int V) {
        this.V = V;
        dist = new int[V][V];
        
        // Initialize
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (i == j) {
                    dist[i][j] = 0;
                } else {
                    dist[i][j] = INF;
                }
            }
        }
    }
    
    public void addEdge(int u, int v, int weight) {
        dist[u][v] = weight;
    }
    
    // Floyd-Warshall: All pairs shortest path
    public void floydWarshall() {
        // For each intermediate vertex
        for (int k = 0; k < V; k++) {
            // For each pair of vertices
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    // If path through k is shorter
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
    }
    
    public int getDistance(int u, int v) {
        return dist[u][v] == INF ? -1 : dist[u][v];
    }
    
    public static void main(String[] args) {
        FloydWarshall g = new FloydWarshall(4);
        g.addEdge(0, 1, 5);
        g.addEdge(0, 3, 10);
        g.addEdge(1, 2, 3);
        g.addEdge(2, 3, 1);
        
        g.floydWarshall();
        
        System.out.println("All pairs shortest paths:");
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                int d = g.getDistance(i, j);
                System.out.print(d >= 0 ? d + " " : "- ");
            }
            System.out.println();
        }
    }
}