Number of shortest paths in an Undirected Weighted Graph

import java.io.*;

import java.util.*;

class GFG {

  

    

    static class Node implements Comparator<Node> {

  

        

        public int node;

  

        

        

        public int cost;

  

        public Node() {}

  

        

        public Node(int node, int cost)

        {

            this.node = node;

            this.cost = cost;

        }

  

        

        @Override

        public int compare(Node node1, Node node2)

        {

            if (node1.cost < node2.cost)

                return -1;

            if (node1.cost > node2.cost)

                return 1;

            return 0;

        }

    }

  

    

    

    static void addEdge(ArrayList<ArrayList<Node> > adj,

                        int x, int y, int w)

    {

        adj.get(x).add(new Node(y, w));

        adj.get(y).add(new Node(x, w));

    }

  

    

    

    static void dijkstra(ArrayList<ArrayList<Node> > adj,

                         int src, int n, int dist[],

                         int paths[])

    {

        

        

        PriorityQueue<Node> pq

            = new PriorityQueue<Node>(n + 1, new Node());

  

        

        Set<String> settled = new HashSet<String>();

  

        

        pq.add(new Node(src, 0));

  

        dist[src] = 0;

        paths[src] = 1;

  

        

        while (!pq.isEmpty()) {

  

            

            int u = pq.peek().node;

  

            

            

            int d = pq.peek().cost;

  

            

            pq.poll();

  

            for (int i = 0; i < adj.get(u).size(); i++) {

                int to = adj.get(u).get(i).node;

                int cost = adj.get(u).get(i).cost;

  

                

                if (settled.contains(to + " " + u))

                    continue;

  

                

                

                if (dist[to] > dist[u] + cost) {

  

                    

                    pq.add(new Node(to, d + cost));

  

                    

                    dist[to] = dist[u] + cost;

  

                    

                    paths[to] = paths[u];

                }

  

                

                else if (dist[to] == dist[u] + cost) {

                    paths[to] = (paths[to] + paths[u]);

                }

  

                

                settled.add(to + " " + u);

            }

        }

    }

  

    

    

    static void

    findShortestPaths(ArrayList<ArrayList<Node> > adj,

                      int s, int n)

    {

        

        

        int[] dist = new int[n + 5];

  

        

        

        

        int[] paths = new int[n + 5];

  

        for (int i = 0; i <= n; i++)

            dist[i] = Integer.MAX_VALUE;

  

        for (int i = 0; i <= n; i++)

            paths[i] = 0;

  

        

        

        dijkstra(adj, s, n, dist, paths);

  

        System.out.print("Shortest Paths distances are : ");

        for (int i = 1; i <= n; i++) {

            System.out.print(dist[i] + " ");

        }

  

        System.out.println();

  

        System.out.print(

            "Numbers of the shortest Paths are: ");

        for (int i = 1; i <= n; i++)

            System.out.print(paths[i] + " ");

    }

  

    

    public static void main(String[] args)

    {

        

        int N = 9;

        int M = 14;

  

        ArrayList<ArrayList<Node> > adj = new ArrayList<>();

  

        for (int i = 0; i <= N; i++) {

            adj.add(new ArrayList<Node>());

        }

  

        addEdge(adj, 1, 2, 1);

        addEdge(adj, 2, 3, 1);

        addEdge(adj, 3, 4, 2);

        addEdge(adj, 4, 5, 1);

        addEdge(adj, 5, 6, 2);

        addEdge(adj, 6, 7, 2);

        addEdge(adj, 7, 8, 1);

        addEdge(adj, 8, 1, 1);

        addEdge(adj, 2, 8, 2);

        addEdge(adj, 3, 9, 1);

        addEdge(adj, 8, 9, 2);

        addEdge(adj, 7, 9, 2);

        addEdge(adj, 3, 6, 1);

        addEdge(adj, 4, 6, 1);

  

        

        findShortestPaths(adj, 1, N);

    }

}

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets