Live briefing
Everything about Shortest path problem
Computational problem of graph theory
In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Shortest path problemA 5-minute orientation
- Skim a recent paper: Data-Driven Optimization for Dynamic Shortest Path Problem Considering Traffic SafetyInfluential work since 2022
- Pick up a classic book: Combinatorial Reciprocity TheoremsThe most-reprinted book on the subject
- Read the landmark paper: Faster algorithms for the shortest path problemCited 372 times
- Go sideways: Maximum-cardinality matchingA closely related topic
- Go sideways: Widest path problemA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🏆 Landmark papers (most cited)
Faster algorithms for the shortest path problem
On a multicriteria shortest path problem
On the Robust Shortest Path Problem
Shortest path problem with uncertain arc lengths
The Variance-Constrained Shortest Path Problem
The shortest path problem with forbidden paths
The dynamic shortest path problem with anticipation
An inverse problem of the weighted shortest path problem
🆕 Influential since 2022
Data-Driven Optimization for Dynamic Shortest Path Problem Considering Traffic Safety
An improved weighted sum-fuzzy Dijkstra’s algorithm for shortest path problem (iWSFDA)
An Efficient Label-Correcting Algorithm for the Multiobjective Shortest Path Problem
Interval-Valued Fermatean Neutrosophic Shortest Path Problem via Score Function
Constrained shortest path tour problem: Branch-and-Price algorithm
📚 Books worth reading
- 📕Combinatorial Reciprocity TheoremsMatthias Beck, Raman Sanyal · 2019
- 📕Mathematical Legacy of Richard P. StanleyPatricia Hersh, Thomas Lam · 2016
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Maximum-cardinality matching In graph theory, a maximum-cardinality matching is a special kind of subgraph useful in many computational contexts. Given a graph G, a matching is a subgraph…
- Widest path problem In graph algorithms, the widest path problem is the problem of finding a path between two designated vertices in a weighted graph, maximizing the weight…
- Maximum flow problem In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate. The maximum…
- Floyd–Warshall algorithm In computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm)…
- Dijkstra's algorithm Dijkstra's algorithm (/ˈdaɪk.strəz/, DYKE-strəz) is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent…
- Steiner tree problem In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of…
- Longest path problem In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph.…
- Betweenness centrality In graph theory, betweenness centrality is a measure of centrality in a graph based on shortest paths. Betweenness centrality measures how frequently a…