When do Dijkstra and the Bellman-Ford algorithm both fail to find a shortest path?

Question

I know Dijkstra fails when there are negative edge weights, but when do both algorithms fail?

Answer 1

If there are negative cycles (reachable from the source), Bellman-Ford can be considered to fail. The main problem with a negative cycle is that you can just keep traversing it, reducing the cost of the path, thus there exists no finite shortest path to some vertices (so it's arguable whether Bellman-Ford actually failed or not - it can detect these cycles).

Dijkstra's algorithm will have a similar problem with negative cycles (not to mention the more general problem of dealing with negative edge weights).

Another scenario can be unreachable vertices, but again you can just detect that they're unreachable.