Algorithms for Finding Shortest Paths Between Points

Finding the shortest path between points is a common problem in computer science, with many practical applications—like navigation, logistics, and network analysis. Here’s an overview of some popular algorithms used to solve this problem, including their formulas, usage scenarios, and main pros/cons.

Summary

Algorithm	Formula	Usage	Pros	Cons
Dijkstra's	dist[v]=min(dist[v],dist[u]+w)	Single-source shortest path (non-negative weights)	Fast for sparse graphs, easy to implement	Cannot handle negative weights; single-source only
Bellman-Ford	dist[v]=min(dist[v],dist[u]+w) (repeat V - 1 times)	Single-source (can handle negative weights)	Handles negative weights, detects cycles	Slower than Dijkstra's; less efficient for large graphs
Floyd-Warshall	dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])	All-pairs shortest path	Handles all pairs, works with negative edges	High memory & computational cost (O(n3)O(n^3)O(n3)); not for large graphs
A*	f(n)=g(n)+h(n)	Pathfinding with heuristics (like maps)	Efficient with good heuristics; fast in practice	Can be less optimal if heuristic is poor

1. Dijkstra’s Algorithm

• Usage: Ideal for finding shortest paths from a single source in graphs without negative weights, such as GPS navigation or network routing.

• Pros:

  • Efficient and easy to implement.

  • Good performance on sparse graphs.

• Cons:

  • Doesn’t work with negative edge weights.

  • Must be run multiple times for all-pairs paths.

2. Bellman-Ford Algorithm

• Usage: Used when graphs contain negative weights—such as currency arbitrage or certain network flows.

• Pros:

  • Handles negative weights.

  • Can detect negative cycles (when no solution exists).

• Cons:

  • Slower than Dijkstra’s; not great for large graphs.

3. Floyd-Warshall Algorithm

• Usage: Computes shortest paths between all pairs of nodes. Used in multi-stop route planning and workload analysis where many paths need to be known at once.

• Pros:

  • Solves the all-pairs problem efficiently for small graphs.

  • Can handle negative edges.

• Cons:

  • High O(n3)O(n^3)O(n3) time and O(n2)O(n^2)O(n2) memory complexity; not suitable for large graphs or real-time systems.

4. A Algorithm*

• Usage: Common in games and mapping software where a heuristic (like straight-line distance) guides the search.

• Pros:

  • Highly efficient if heuristic is good.

  • Flexible in applications needing fast pathfinding.

• Cons:

  • May give suboptimal results if heuristic is bad.

Conclusion

When choosing an algorithm, consider:

• Graph size: Dijkstra’s for sparse, Floyd-Warshall for small all-pairs, Bellman-Ford for negatives.

• Performance needs: Dijkstra’s and A* for speed.

• Edge weights: Bellman-Ford/Floyd-Warshall for negatives; Dijkstra/A* for positives only.

Each algorithm has its strengths and trade-offs; pick the best fit for your data and goals.