# What happens if I replace $<$ with $\le$ in Dijkstra's algorithm?

The following is Dijkstra's algorithm for finding the shortest path in a graph. I know something wrong happens if I replace d[u] + weight(u,v) < d[v] with d[u] + weight(u,v) <= d[v]. What would be an example of the algorithm working incorrectly with that replacement?

def dijkstraShortestPath(G,s,t):
d[v] = Infinity for all v in G.vertices
d[s] = 0
unsureVertices = G.vertices
while len(unsureVertices) > 0:
u = a vertex in unsureVertices so that d[u] is minimized
if d[u] == Infinity:
break
for v in u.getOutNeighbors(): //all v are in unsureVertices
if d[u] + weight(u,v) < d[v]:
d[v] = d[u] + weight(u,v)
v.parent = u
unsureVertices.remove(u)
if d[t] == Infinity:
return "Can't reach t from s!"
path = []
current = t
while current!= s:
path.append(current)
current = current.parent
path.append(current)
path.reverse()
return path

• Can you figure out such an example? If not, can you prove they are equivalent? – John L. Dec 6 '18 at 18:01
• How do you know something wrong happens? It's unclear to me why that would be the case, as it seems this would just prefer shortest paths with more edges. – ryan Dec 6 '18 at 18:09

I would argue that this does not matter. Consider the case where there are multiple shortest paths from $$s$$ to $$t$$ in $$G$$. In the case of using $$<$$, we define the shortest path to be the first shortest path we come across. This is because latter paths will only be equivalent in length and thus not satisfy the invariant. However, in the case of using $$\leq$$ we define the shortest path to be the last shortest path we come across. This is because latter paths will be equivalent in length and thus trigger the invariant.
My point is that with $$<$$ or $$\leq$$ we could essentially flip the ordering of nodes in the adjacency list of adjacency matrix to mimic what the other comparison operator would do.