ConceptTheory & Algos
Dijkstra's algorithm
An algorithm for finding the shortest paths between nodes in a graph with non-negative edge weights.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Graph3Shortest path3Priority queue2Directed graph1Edge1Graph theory1Greedy algorithm1Non-negative edge weights1
Opens up
Concepts that name this one as a prerequisite.
A* search1Bidirectional Dijkstra search1Bidirectional search1Correctness of Dijkstra's algorithm1Dijkstra's algorithm complexity1Goal-directed search1Inductive step for Dijkstra's correctness1Johnson's algorithm1Landmark heuristic1Path reconstruction set E tilde1Planar graph algorithms1Prim's algorithm running time1
Lecturers
4Each in their own terms, from the easiest level.
UC Davis Academics
An algorithm for computing the shortest distance from a fixed initial node s to every other node v in a directed graph with non-negative edge lengths.Srini Devadas
A greedy algorithm that finds the shortest paths from a source vertex to all other vertices in a graph with non-negative edge weights.Han Huang
An algorithm for finding the shortest paths between nodes in a graph.
Lectures that assume it
5Connections
19The lectures that define it or assume it, and the concepts next to it.
Concepts10
Lectures9
- Dijkstra's Shortest Path Algorithm: Graph Theory and Optimization
- Dijkstra's Algorithm: Greedy Single-Source Shortest Paths
- Dynamic Programming: All-Pairs Shortest Paths
- Recovering Riemannian Metric Distance from Random Geometric Graphs
- Greedy Algorithms: Minimum Spanning Tree
- Markov Decision Processes (MDPs) Part 2/2