Shortest path algorithm

In graph theory [Graph theory], the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

Algorithms

• Single-source shortest path problem
  • Non-negative weights: Dijkstra’s algorithm, A*
  • Negative weights: Bellman-Ford algorithm
• Single-pair shortest path problem
  • Non-negative weights: Dijkstra’s algorithm
  • Negative weights: Bellman-Ford algorithm
• All-pairs shortest path problem
  • Floyd-Warshall algorithm

Backlinks

• Single-pair shortest path problem
• All-pairs shortest path problem
• Widest path problem
• Directed acyclic graph
• Single-source shortest path problem
• December 2022
• Dijkstra’s algorithm
• Ali Kemal Sinop, Lisa Fawcett, Sreenivas Gollapudi, Kostas Kollias | Robust Routing Using Electrical Flows
• Todos
• Contraction hierarchies