Java Solution Dijkstra using Min Heap with extensive Comments. Hope it helps...
\tclass Solution {\n\t\tpublic int countPaths(int n, int[][] roads) {\n\t\t\tList[] graph = constructGraph(n, roads); // returns adjacency List for given road[]
\tclass Solution {\n\t\tpublic int countPaths(int n, int[][] roads) {\n\t\t\tList<Edge>[] graph = constructGraph(n, roads); // returns adjacency List for given road[][]\n\n\t\t\tPriorityQueue<Pair> pq = new PriorityQueue<>();\n\t\t\tint[] dist = new int[n]; // dist array stores the min. cost/weight/time to reach from sourceVtx(0) to every other node in the graph\n\t\t\tArrays.fill(dist, Integer.MAX_VALUE); // since we want to calculate the Min. distance/time ..intialize each dist[i] with infinity.\n\n\t\t\tint[] path = new int[n]; // this is the extra storage which stores the count of paths from src to every other node in the graph\n\n\t\t\tpq.add(new Pair(0, 0)); // Pair(vtx, weight)\n\t\t\tdist[0] = 0; // we are starint from source : 0, therefore 0 distance/cost/time to reach 0 from 0.\n\t\t\tpath[0] = 1; // Initial/Base Value  for source vtx : 1 path to reach source while standing on source.\n\n\t\t\tint modVal = (int)1e9 + 7; // required by question.\n\t\t\twhile(pq.size() > 0) {\n\t\t\t\tPair rem = pq.remove();\n\n\t\t\t\tfor(Edge e : graph[rem.vtx]) {\n\t\t\t\t\tint nbr = e.nbr; // V\n\t\t\t\t\tint nbrdist = e.wt; // nbrdist is the wt between rem.vtx(U) and its neighbour(V)\n\t\t\t\t\tif(rem.wsf + nbrdist < dist[nbr]) { // if this conditions is true : it means we are on a path which reach neighbour of rem.vtx i.e U at a lesser cost/time that what is stored in the distance array for this neighbour... so update it and add neighbour im queue\n\t\t\t\t\t\tdist[nbr] = rem.wsf + nbrdist;\n\t\t\t\t\t\tpath[nbr] = path[rem.vtx]; // this line means that if we can reach node : U in X ways then we can also reach the neighbours of U in X ways.... therefore path[nbr] = path[U] U here means rem.vtx\n\t\t\t\t\t\tpq.add(new Pair(nbr, dist[nbr]));\n\t\t\t\t\t} else if(rem.wsf + nbrdist == dist[nbr]) {\n\t\t\t\t\t// this check denotes that we came at this nbr previously and now again at same cost as previous time...\n\t\t\t\t\t// therefore we have explored a new path for reaching this nbr via current vtx i.e U....\n\t\t\t\t\t// therefore new ways of reaching nbr would be path[nbr] + path[rem.vtx]  (Basic DP structure, dry run it once, you will get it)\n\t\t\t\t\t\tpath[nbr] += path[rem.vtx]; \n\t\t\t\t\t\tpath[nbr] = path[nbr] % modVal;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\n\t\t\treturn path[n-1]; // n-1 is the destination vtx\n\t\t}\n\n\t\t// this class is for BFS traversing using MinHeap \n\t\tprivate class Pair implements Comparable<Pair>{ \n\t\t\tint vtx;\n\t\t\tint wsf;\n\t\t\tPair(int vtx, int wsf) {\n\t\t\t\tthis.vtx = vtx;\n\t\t\t\tthis.wsf = wsf; // weightSoFar\n\t\t\t}\n\n\t\t\tpublic int compareTo(Pair o) {\n\t\t\t\treturn this.wsf - o.wsf;\n\t\t\t}\n\t\t}\n\n\t\tprivate class Edge {\n\t\t\tint src; // U\n\t\t\tint nbr; // V\n\t\t\tint wt; // cost of travelling from U to V or vice versa\n\t\t\tEdge(int src, int nbr, int wt) {\n\t\t\t\tthis.src = src;\n\t\t\t\tthis.nbr = nbr;\n\t\t\t\tthis.wt = wt;\n\t\t\t}\n\t\t}\n\n\t\tprivate List<Edge>[] constructGraph(int n, int[][] roads) {\n\t\t\tList<Edge>[] graph = new ArrayList[n];\n\n\t\t\tfor(int i = 0; i < n; i++) { // initializing graph[] with empty arrayLists\n\t\t\t\tgraph[i] = new ArrayList<>();\n\t\t\t}\n\n\t\t\tfor(int i = 0; i < roads.length; i++) {\n\t\t\t\tint u = roads[i][0];\n\t\t\t\tint v = roads[i][1];\n\t\t\t\tint wt = roads[i][2];\n\n\t\t\t\tgraph[u].add(new Edge(u, v, wt)); // add Edge at Uth node which goes from U to V at wt cost\n\t\t\t\tgraph[v].add(new Edge(v, u, wt)); // add Edge at Vth node which goes from V to U at wt cost\n\t\t\t}\n\t\t\treturn graph;\n\t\t}\n\t}
[]