How would Dijkstra change if we use the less than sign in the code?

Question

Suppose we alter Dijkstra’s algorithm so that instead of the < sign, we replace it with the > sign. Let G be a directed graph that contains no cycles. Does this new version find the longest path from the source vertex to every other vertex in the graph? Justify your answer.

Answer 1

Here are the rough steps of Dijkstra's Algorithm from Wikipedia (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Pseudocode):

1 function Dijkstra(Graph, source):

2

3 for each vertex v in Graph.Vertices:

4 dist[v] ← INFINITY

5 prev[v] ← UNDEFINED

6 add v to Q

7 dist[source] ← 0

8

9 while Q is not empty:

10 u ← vertex in Q with min dist[u]

11 remove u from Q

12

13 for each neighbor v of u still in Q:

14 alt ← dist[u] + Graph.Edges(u, v)

15 if alt < dist[v]:

16 dist[v] ← alt

17 prev[v] ← u

18

19 return dist[], prev[]

I am assuming you are asking what will happen if we change the "<" on line 15 to ">". If that happens, then the if statement on line 15 is never executed, since nothing is greater than infinity. In that case, the new version does not produce the longest path from the source to every other vertex, because every vertex is set to infinity, and that'll never change. In short, changing the "<" on line 15 to ">" only makes the algorithm return nothing useful, not the longest path.

If you need more help with Dijkstra's algorithm in general, I am happy to walk through it with you! Just book a session with me and I will walk through it and explain it until you understand. Right now I am still offering heavily discounted price because I am new to this Wyzant (but not new to tutoring!). Eventually, I will raise it to my regular rate, so book soon!