CSE 373 Lecture Notes - Lecture 11: Shortest Path Problem, List Of Algorithms, Glossary Of Graph Theory Terms
CSE 373 Lecture 11
Graph algorithms
- Traversing a graph
o
o
o Depth first search:
▪ Both similar runtime, one uses stack, 1 uses queue
o Path length – sum of edge weights on ph
o Shortest Path Problem
▪ Given: directed graph G and vertices s and t
▪ Find: shortest path from s to t