WhiteBox
DSA
Start coding DSA Beyond LeetCode System Design AI Engineering White Room
RoadmapProblem sets
Quizzes Dan Ladder Contests Templates Graph Editor
Guides Library
Login Sign up
Sign up Log in

Workspaces

Start coding DSA Beyond LeetCode System Design AI Engineering White Room

DSA

Overview Roadmap Problem sets Quizzes Dan Ladder Contests Templates Graph Editor CP Guessr

Library

Library Guides

Community

Leaderboard Contributors Refer & Earn Cosmetics

Tools

Resume Reviewer Job Boards Changelog

Graphs 0/61

DSA 0 of 360 problems solved
0%
Overview

Curriculum

    1. BFS 0/10
    2. DFS 0/13
    3. Grid traversal 0/10
    4. Topological sort 0/11
    5. Union-find (DSU) 0/10
    6. Dijkstra and shortest paths 0/8
      1. Shortest paths in weighted graphs
      2. Dijkstra 0/8
      3. Bellman-Ford
      4. Floyd-Warshall
  1. DSA
  2. / Graphs

Dijkstra and shortest paths · 1 of 4

Shortest paths in weighted graphs

Define the length of a path and the distance in a weighted graph, see what BFS can and cannot do with weights, and find distances by relaxing every edge in rounds.

2,415 words · 11 min read

Lesson Reading3

Books1

  • Competitive Programmer’s Handbook, Chapter 13: Shortest paths Pages 123 to 131 step through Bellman-Ford, Dijkstra and Floyd-Warshall on small drawn graphs, and show a negative edge that defeats Dijkstra. (opens in a new tab)

Links2

  • usaco.guide Shortest Paths with Non-Negative Edge Weights Solves CSES Shortest Routes I with Dijkstra and Shortest Routes II with Floyd-Warshall, and has a graded list of problems to practice on. usaco.guide (opens in a new tab)
  • oi-wiki.org 最短路 (Shortest paths) Floyd, Bellman-Ford with its queue variant SPFA, Dijkstra with a correctness proof, Johnson’s algorithm and a table comparing all of them. oi-wiki.org (opens in a new tab)
Lesson: Shortest paths in weighted graphs
Overview Roadmap Problem sets Log in