How to solve this google coding round problem?

Revision en6, by destiny____, 2021-11-08 20:01:55

Given an undirected weighted 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?

Tags help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English destiny____ 2021-11-08 20:06:34 2 Tiny change: 'irected **weighted**' -> 'irected **unweighted**'
en6 English destiny____ 2021-11-08 20:01:55 154
en5 English destiny____ 2021-11-08 19:59:22 17
en4 English destiny____ 2021-11-08 19:58:45 13 Tiny change: 'rs in the path from root to t' -> 'rs in the shortest path from the root to t'
en3 English destiny____ 2021-11-08 19:58:12 11 Tiny change: 'let's say graph is ' -> 'let's say the graph is '
en2 English destiny____ 2021-11-08 19:57:32 222
en1 English destiny____ 2021-11-08 19:54:53 230 Initial revision (published)