P-5.6 Graph Algorithms

Work through these

• Depth-first traversal, and what it is good at finding

  Going as deep as possible before backing up detects cycles, finds connected components and orders dependencies. It is naturally recursive and short.

  NPTEL: Data Structures and Algorithms · Course

• Breadth-first traversal, and why it gives shortest paths when edges are equal

  Visiting everything one step away, then two, reaches each vertex by the fewest edges possible. With no weights involved this is already the shortest-path answer.

• Ordering dependent tasks, and detecting that it is impossible

  A build order, a course prerequisite listing and a spreadsheet recalculation are the same problem. If the graph contains a cycle no valid order exists, and the algorithm reports that rather than guessing.

• Dijkstra for non-negative weights, using a heap

  Always expanding the nearest unfinished vertex gives shortest paths when no edge has negative cost. The heap from the previous module is what makes it efficient.

• Negative weights, and why Dijkstra is wrong there

  A negative edge can make a longer route cheaper later, which breaks the assumption that a settled vertex stays settled. Bellman-Ford handles it and also detects negative cycles.

  Algorithms · Reference