Basic Graph Algorithms

BFS

{

        Deque queue = new ArrayDeque<Integer>();

        int vis[] = new int[v];
 
        // and as no path is yet constructed
        // dist[i] for all i set to infinity
        Arrays.fill(pred, -1);
        Arrays.fill(dis, Integer.MAX_VALUE);
 
        // now source is first to be visited and
        // distance from source to itself should be 0
        vis[src] = 1;
        dist[src] = 0;
        queue.add(src);
 
        // bfs Algorithm
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int i = 0; i < adj.get(u).size(); i++) {
                if (vis[adj.get(u).get(i)] == false) {
                    vis[adj.get(u).get(i)] = true;
                    dist[adj.get(u).get(i)] = dist[u] + 1;
                    pred[adj.get(u).get(i)] = u;
                    queue.add(adj.get(u).get(i));
 
                    // stopping condition (when we find
                    // our destination)
                    if (adj.get(u).get(i) == dest)
                        return true;
                }
            }
        }
        return false;
    }

DFS

dfs(String a, String b, Set<String> vis){
        if(vis.contains(a)) return -1;

        if(a.equals(b)) return 1;

        vis.add(a);
        for(Pair p: mp.get(a)){
            if(!vis.contains(p.op)){
               int ans = dfs(p.op, b, vis);
               // If found return
               if(ans != -1) return ans  * p.val;
            }
        }
        return -1;
    }

Single source shortest path

Dijkstra

        Queue<int[]> q = new PriorityQueue<>((a,b) -> a[1]- b[1]);
        long dis[] = new long[N];
        Arrays.fill(dis, inf);
        if(adj[0] == null) return -1;

        q.offer(new int[]{0,0});
        dis[0] = 0;

        while(!q.isEmpty()){
            int[] s = q.poll();
            if(adj[s[0]] == null) continue;
         
            for(int[] p : adj[s[0]]){
                if(dis[s[0]] + p[1] < dis[p[0]]){
                     dis[p[0]] = dis[s[0]] + p[1];
                     q.offer(new int[]{p[0], (int)dis[p[0]]});
                }

            }

        }

All Pair shortest path

Floyd — Warshall

        for (k = 0; k < V; k++) {
            // Pick all vertices as source one by one
            for (i = 0; i < V; i++) {
                // Pick all vertices as destination for the
                // above picked source
                for (j = 0; j < V; j++) {
                    // If vertex k is on the shortest path
                    // from i to j, then update the value of
                    // dist[i][j]
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        
                        dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }

All Pair shortest path with K edges

        int[][] adj = new int[n][n];
        for(int[] g: adj){
            Arrays.fill(g, inf);
        }

        for(int[] s: flights){
            adj[s[0]][s[1]]=s[2];
        }

        int[][][] dp = new int[n][n][k+1];
        for(int e = 0; e <= k; e++){
            for(int i = 0; i< n ; i++){
                for(int j = 0 ; j < n ; j++){
                    dp[i][j][e] = inf;

                    // Self loop detection
                    if(e==0 && i==j){
                        dp[i][j][e] = 0;
                    }
                    
                    // src -> dest check
                    if( e == 1 && adj[i][j] != inf){
                        dp[i][j][e] = adj[i][j];
                    }

                    if(e>1){
                        // should be a (e-1 edges + weight) in other nodes
                        for(int x = 0; x< n ; x++){
                            if(adj[i][x] != inf && x != i ){
                                dp[i][j][e] = Math.min(dp[i][j][e] , dp[x][j][e-1] + adj[i][x]);
                            }
                        }
                    }
                }
            }
        }