Problem $4$

You are given a network of $n$ nodes $\{v_1,v_2,$dots,$v_n\}$ and $m$ directed edges $\{e_1,e_2,$dots,$e_m\}.$ Each directed

edge $e_i$ has start vertex $s_i,$ end vertex $t_i,$ and communication time $w_i.$ The communication time $w_i$ is how

long it takes for a message to be transferred from $s_i$ to $t_i.$

You are given a node $v_j,$ which is given some information at time $0.$ We wish for all nodes to receive this

information. Any node that gets information may immediately transfer this message onto all of its outgoing

edges simultaneously. For example, if $v_1$ gets the information at time $w,$ and it has an outgoing edge with

communication time $w_k$ to $v_2,$ then $v_2$ will receive the information at time $w+w_k,$ if it does not receive it

sooner from one of its other neighbors.

Design an efficient algorithm that, given the network and the start node $v_j,$ will find the minimum time

it takes for all the $n$ nodes to receive the information if it is possible for all the $n$ nodes to receive the signal.