destiny____'s blog

How to solve this google coding round problem?
By destiny____, history, 3 years ago, In English

Given an undirected unweighted graph with n nodes rooted at node 1. In this graph for each node we've to find the number of predecessors in the shortest path from the root to this node. Any ideas?

let's say the graph is like this

                 1
                / \
               2   4
               \  /
                3

Here for node 3 predecessors are 2 and 4

My initial thoughts: I thought of applying Dijkstra but we can't find all the shortest paths using Dijkstra. Anyone has different thoughts then mine?

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

HINT: Apply BFS, and maintain a distance vector simultaneously. If dist[from] + 1 == dist[to] then predecessor[to]++.

→ Reply