Reachable nodes in the new graph

Create the new graph from the original graph by adding the chain nodes. The problem becomes finding the number of nodes whose shortest path from node ‘0’ is less than equal to ‘m’. As the new graph is unweighted, we can use Breadth-first search (BFS) traversal to find the shortest path. The shortest path length will be equivalent to the node’s level in the BFS traversal tree. Perform BFS up to level ‘m’, as we only want the nodes with path length less than equal to ‘m’.
 

Proof of correctness: As we move level-wise in BFS, if a child node is not visited, it’s not reachable from any previous levels. Its shortest path will be equal to (parent node’s level + 1). Even if it’s reachable from any other node from the next levels, the corresponding path length will always be greater.
 

Following is an implementation of BFS to solve this problem:
 

• Set ‘id = n’. Use this as the node number for the chain nodes.
• Run a loop where ‘i’ ranges from ‘0’ to ‘numOfPairs - 1’:
  • ‘n += edges[i][2]’. Calculate the number of nodes in the new graph by adding the number of chain nodes.
• Create an adjacency list ‘graph[n]’. Use it to store the new graph.
• Run a loop where ‘i’ ranged from ‘0’ to ‘numOfPairs - 1’, add the chain nodes:
  • Set ‘l = e[0]’ and ‘r = id’.
  • Run a loop where ‘j’ ranges from ‘0’ to ‘edges[i][2] - 1’:
    • ‘graph[l].append(r)’
    • ‘graph[r].append(l)’
    • ‘id += 1’. The node number for the next node in the chain.
    • ‘l = r’ and ‘r = id’
  • ‘graph[edges[i][1]].append(l)’
  • ‘graph[l].append(edges[i][1])’
• Create an empty queue ‘bfsQ’. Use it to perform the BFS traversal.
• Create an array ‘seen[n]’ set to ‘false’. Use it to track visited nodes.
• ‘bfsQ.push(0)’ and ‘seen[0] = true’. As ‘0’ is the source node.
• Set ‘res = 1’, and ‘lvl = 0’. Use ‘res’ to store the number of reachable nodes and ‘lvl’ to store the current BFS level.
• Run a loop while (‘bfsQ’ is not empty) and (‘lvl’ is not equal to ‘m’):
  • Set ‘sz = size(bfsQ)’. Here, ‘sz’ is the number of nodes at level ‘lvl’.
  • Run a loop where ‘i’ ranges from ‘i’ to ‘0’ to ‘sz - 1’. The nodes remaining in ‘bfsQ’ after ‘sz’ iterations belong to the next level:
    • ‘cur = bfsQ.pop()’
    • Run a loop where ‘j’ ranges from ‘0’ to ‘length(graph[cur]) - 1’:
      • ‘next = graph[cur][j]’
      • If ‘seen[next]’ is ‘false’, then we have not visited the node ‘next’:
        • ‘bfsQ.push(next)’
        • ‘seen[next] = true’
        • ‘res++’. Node ‘next’ is reachable from node ‘0’.
  • ‘lvl += 1’. Move to the next level, until level ‘m’.
• Return ‘res’ as the answer.

Consider the given graph as a weighted and undirected graph. For any edge ‘(u, v, sz)’ in the distance between ‘u’ and ‘v’ in the new graph is ‘sz + 1’ as there are ‘sz’ nodes in the chain between ‘u’ and ‘v’. So, the edge between ‘(u, v)’ has a weight equal to ‘sz + 1’. Now, we can use Dijkstra’s algorithm to find all reachable nodes in the original graph. However, this will be less than the final answer as we are not counting the partial chain of nodes in the answer.
 

When we reach a node using the shortest path ‘dist[i]’, we can still move ‘m-dist[i]’ edges from the current node. In the end, for every edge ‘(u, v, sz)’, node ‘u’ can visited ‘l’ (‘= m - dist[u]’) and ‘v’ can visit ‘r’ (‘= m - dist[v]’) chain nodes along the edge ‘(u, v)’. So, the number of chain nodes that we can visit along ‘(u, v)’ is equal to ‘min(sz, l + r)’.
 

Following is an implementation of Dijkstra’s algorithm using a priority queue (in this case, a min-heap) to solve this problem:

• Create an adjacency list ‘graph[n]’. Use it to store the given graph.
• Run a loop where ‘i’ ranged from ‘0’ to ‘numOfPairs - 1’:
  • ‘u = edges[i][0]’, ‘v = edges[i][1]’ and ‘sz = edges[i][2]’
  • ‘graph[u].append({v, sz})’. Add an edge from ‘u’ to ‘v’ with weight ‘sz’.
  • ‘graph[v].append({u, sz})’. Add an edge from ‘v’ to ‘u’ with weight ‘sz’.
• Create an empty priority queue ‘pq’ that stores elements of the form ‘(x, y)’. The element with a smaller value of ‘x’ has higher priority.
• Create an array ‘dist[n]’ to store the shortest path length. Set it to ‘m+1’, as all nodes are unreachable initially.
• ‘pq.push({0, 0})’ and ‘dist[0] = 0’. As ‘0’ is the source node.
• Set ‘count = 0’. Use ‘count’ to count the number of reachable nodes.
• Run a loop while ‘pq’ is not empty:
  • Set ‘{moves, u} = pq.pop()’. Here, ‘moves’ is the length of the path to reach node ‘u’.
  • If ‘moves > dist[u]’, then ‘moves’ is not the shortest path:
    • Continue the loop to the next iteration.
  • ‘count += 1’. As node ‘u’ is reachable.
  • Run a loop where ‘i’ ranges from ‘0’ to ‘length(graph[u]) - 1’:
    • ‘next = graph[u][j][0]’
    • ‘nextMoves = moves + graph[u][i][1] + 1’. Here, ‘nextMoves’ is the distance to reach the node ‘next’ through the node ‘u’.
    • If ‘nextMoves < dist[next]’, then this is a shorter path to reach ‘next’:
      • ‘dist[next] = nextMoves’
      • ‘pq.push({nextMoves, next})’
• Run a loop where ‘i’ ranges from ‘0’ to ‘numOfPairs - 1’, find the number of reachable chain nodes:
  • ‘u = edges[i][0]’ and ‘v = edges[i][1]’
  • Set ‘l = 0’ and ‘r = 0’.
  • If ‘dist[u] != m + 1’, then node ‘u’ is reachable:
    • ‘l = m - dist[u]’. Number of chain nodes reachable from ‘u’.
  • If ‘dist[v] != m + 1’, then node ‘v’ is reachable:
    • ‘r = m - dist[v]’. Number of chain nodes reachable from ‘v’.
  • ‘count += min(l + r, edges[i][2])’. Chain nodes on edge ‘(u, v)’ that are reachable.
• Return ‘count’ as the answer.