- Graph, Shortest Path

Number of shortest paths in an Undirected Weighted Graph

import java.io.*;import java.util.*;class GFG {          static class Node implements Comparator {                  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 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 adj,                         int src, int n, int dist[],                         int paths[])    {                        PriorityQueue pq            = new PriorityQueue(n + 1, new Node());                  Set settled = new HashSet();                  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 adj,                      int s, int n)    {                        int[] dist = new int[n + 5];                                  int[] paths = new int[n + 5];          for (int i = 0; i