18.100C Lecture Notes - Lecture 2: Ath, Spanning Tree
Document Summary
Dijkstra"s algorithm is a greedy algorithm that looks to nd the shortest path from a secure vertex in the graph whivh produced a shortest spanning tree. G = (v, e, w) where w is the weight function. Shortest tree path: spanning tree with a path back to the source. Not allowed to have negative edge weights d[v] = current length seen so far from s to v. (s, v) = shortest path from s to v. Proof by contradiction d[v] (s, u) initialize: d[s] = 0 if [d]v > d[v] + w(u, v), then set d[v] = d[u] + w(u,v) and (v) = d[v] This will terminate when d[v] d[v] + w(u,v) While q is not empty, nding the minimum d[v] and extract q , put it in s. For each vertex adjacent to u, preform the relaxation. For any shortest path in g, a subgraph of this path is also a shortest path.
