3 ms·
Use Floyd Warshall if you can pre-compute. It pre-computes all the paths from all nodes to all nodes, and it's incredibly efficient. Most awesome algorithm ev
by user5994461 10y ago
Use Floyd Warshall if you can pre-compute.
It pre-computes all the paths from all nodes to all nodes, and it's incredibly efficient.
Most awesome algorithm ever :D
https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorit...
- user5994461 10y agoAnd if you need dynamic graph with variable weighting and nodes, that's a case for D* Mostly used for drone/rover/robot navigation in open environments, with the graphs evolving as the robot discover the environment. https://en.wikipedia.org/wiki/D* https://en.wikipedia.org/wiki/D*
- Schwolop 10y agoOnly if the area changing is near the start of the search, not near the goal. (i.e. near the sensors of a mobile robot, rather than near the destination far from the robot). D* can be pathologically slower than repeated A* searches under such conditions.
- kunaltyagi 10y agoI've been using a modified D*. It increases the grid size as the path moves out of the robot's observable area. This allows a fast search even when the goal is in a environment with known dynamic obstacles. Ideally speaking, you need to plan in higher dimensions to get an optimal path in dynamic environments