A friend wants help in implementing an algorithm for finding the shortest path between two nodes 𝑢 and 𝑣 in a directed graph (possibly containing negative edge weights). He/she proposes the following:
- Add a large constant to each weight such that all weights become positive
- Run Dijkstra’s algorithm for the shortest path from 𝑢 to 𝑣
This method is not correct as it may not always work for all cases. A counterexample for when this method does not work:
Assume we have a start point “𝑢” and an end point "𝑣" with "𝑛" vertices/nodes.
Path 1:
−3 8
𝑢 → 𝑎 → 𝑣
Length of path 1: −3 + 8 = 5
Path 2:
−3 3 4
𝑢 → 𝑎 → 𝑏 → 𝑣
Length of path 2: −3 + 3 + 4 = 4
We can see that path 2 is the shorter path. Now, we add the largest constant (in both cases −3) in both the paths!
Path 1:
0 11
𝑢 → 𝑎 → 𝑣
Length of path 1: 0 + 11 = 11
Path 2:
0 6 7
𝑢 → 𝑎 → 𝑏 → 𝑣
Length of path 2: 0 + 6 + 7 = 13
Now, in this case, when we add a positive large constant in both paths, path 1 is the shorter path. Therefore, we disprove the correctness of the given algorithm using a simple counter example!
Problem 12.2
Implemented in “OMP.cpp”. Execute make to run.
Problem 12.3
a.
The problem given to us can be represented as a graph problem.
i. Consider our board B.
ii. B has coordinates B[x][y] that represents the position of the player. iii. Every coordinate B[x][y] (position) in the board is a node.
iv. All edges are 1 as the distance moved is 1 (in all directions form the current position)
v. The vertex 𝑉 = {0, 1, 2, .… , 𝑛2 – 1} vi. Edges of vertex 𝑉 are neighboring nodes, i.e. up, down, left, right.
