Bender - Episode 2 - Puzzle discussion


#42

Dijkstra algorithm is for finding the shortest path in the graph - that is the one with the minimum sum of edge weights. Another constraint is that all weights must be non-negative. This is coming from how the algorithm works (by gradually extending the current path in a BFS manner using edge weight as priority/order).
The wikipedia article is quite detailed: https://en.wikipedia.org/wiki/Dijkstra's_algorithm

Here we need the maximum cost path of the graph which is different from the minimum. If you simply multiply all weights by (-1), then minimum becomes maximum, but then your weights will become negative and the algo will fail. You can use Floyd-Warshall or Bellman-Ford algorithms (see https://en.wikipedia.org/wiki/Floyd–Warshall_algorithm, https://en.wikipedia.org/wiki/Bellman–Ford_algorithm for explanation and pseudocode) to find the minimum cost path of the graph with negative weights, but these algorithms are computationally more complex than Dijkstra. For me, they timeouted above 5000 rooms.

In the end, a simple DFS with some memoization was the working AND fast-enough solution for me, and not any of these generic graph algorithms.