How to solve this google coding round problem?

Правка en7, от destiny____, 2021-11-08 20:06:34

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?

Теги help

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский destiny____ 2021-11-08 20:06:34 2 Tiny change: 'irected **weighted**' -> 'irected **unweighted**'
en6 Английский destiny____ 2021-11-08 20:01:55 154
en5 Английский destiny____ 2021-11-08 19:59:22 17
en4 Английский 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 Английский destiny____ 2021-11-08 19:58:12 11 Tiny change: 'let's say graph is ' -> 'let's say the graph is '
en2 Английский destiny____ 2021-11-08 19:57:32 222
en1 Английский destiny____ 2021-11-08 19:54:53 230 Initial revision (published)