Problem $2.$ You are given a directed, weighted graph $G=(V,E)$ with $n$ nodes and $m$ edges. Each edge $(u,v)inE$ has a positive integer weight $w(u,v).$ Let $s_1$ and $s_2$ be two designated source nodes in the graph. You need to determine the shortest path distance from either $s_1$ or $s_2$ to each other node vinV, i$.$e$.,$ for each node $v,$ calculate:

$d(v)=$min$(d_{s_1}(v),d_{s_2}(v)),$

where $d_{s_1}(v)$ is the shortest path distance from $s_1$ to $v,$ and $d_{s_2}(v)$ is the shortest path distance from $s_2$ to $v.$

$1$

$($a$)(5$ points$)$ Suppose all edges have positive weights and suppose you are allowed to relax each edge twice. Describe a simple adaptation of Dijkstra's algorithm for this problem.

$($b$)(10$ points$)$ Suppose all edges have positive weights and suppose you are allowed to relax each edge at most once. Describe a modification of Dijkstra's algorithm for this problem using a single priority queue.