3 ms·
I solved it without using Dijkstra's algorithm. I simply used a matrix and updated the minimum distance looking at the four neighbours over and over again, unti
by fjfaase 5y ago
I solved it without using Dijkstra's algorithm. I simply used a matrix and updated the minimum distance looking at the four neighbours over and over again, until no updates were made. (I have no idea how to do this in Haskell.) It is a rather dumb algorith and looks not very efficient, but it does not require you to keep a set of unvisted nodes and their smallest tentative distance.
- hexomancer 5y agoThis approach is pretty well-known. See Bellman-Ford [1] and Floyd-Warshall [2] algorithms. [1] https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm [2] https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorit...