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