1
$\begingroup$

Suppose we have a directed, weighted graph, $G = (V, E, w)$, with non-negative weights. We define the weight of the shortest path different from the original definition.
The weight of a path with at most 5 edges (including 5) will be defined as usual, meaning the sum of the edges weights. The weight of a path with at least 6 edges will be the sum of the edges weights multiplied by 2.
Propose and analyze an efficient algorithm (as you can), That given a graph $G$ and two vertices $u, v$, the algorithm will find the shortest path from $u$ to $v$, as we defined the paths weights. Describe in words why the algorithm works and analyze it's runtime.
My thought was to run first $BFS$ on the graph and for every edge that in a path with 6 or more edges, just multiply the edge weight by 2, and then run dijkstra, but I think it won't work. So then I was tending to do a brute force algorithm and find all the paths from $u$ to $v$ and then find the shortest one, but it is not efficient. So I'm stuck on an answer to this one and would glad for some help.

$\endgroup$

1 Answer 1

1
$\begingroup$

You can take this approach:
Step one:
Duplicate G's nodes 6 times to get a new directed graph with 6 levels $L_1,...,L_6.$
For $1\le i\le5$ and nodes $a,b: $ There will be an edge from $a \in L_i$ to $ b \in L_{i+1} $ if there was an edge from $a$ to $b$ in the original graph, and the weights will be same as the original graph.
From $L_6$ there will be no way to move between the nodes, or to move to any other level.
In this way we can run an SP algorithm from node $u$ in $L_1$ to find the shortest path to $v$ (in any level) with respect to $w$, and each path's length will be no longer than 5.
Assume that we got a shortest path $s_1$ (if no path was found $s_1 = \infty).$
Step two:
Create a new weight function $f(w)=2w$ for the original graph's weights and run Dijkstra's again on the original graph with the new weight function to get another shortest path $s_2$ (again if no path was found $s_2 = \infty).$
Step Three:
return $\min\{s_1,s_2\}.$

Time complexity is that of Dijkstra's since constructing the graph in step 1 takes linear time.

$\endgroup$
3
  • $\begingroup$ I think that I got you. Anyway, with this idea, can't we just run dijkstra one time, and then check if the path is shorter than 5 edges. If so, we are done, else run again with f(w) = 2w and then take the min? $\endgroup$ Jun 4 at 16:37
  • $\begingroup$ Instead of building a new graph with 6 levels $\endgroup$ Jun 4 at 16:40
  • $\begingroup$ @PythonAddict Yes, but like you said- you will need to check that the length of the shortest path does not exceed 5 which is exactly what the new graph does. Also the new graph is a DAG so we can run a faster SP algorithm on it (to get better time complexity on best case). Anyway, time complexity on the worst case will be that of Dijkstra's $\endgroup$
    – NirF
    Jun 4 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.