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? – Apass.Jack Dec 6 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 at 18:09
up vote 0 down vote accepted

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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