Week 9 Notes: Dijkstra's

[varmichelle]

Given a graph and a source vertex, Dijkstra's finds shortest path to all other vertices.
Running time: O(N^2)

1. Build adjacency matrix
2. Create a visited array (initialized to false)
3. Create a distance matrix (populated with distances to each vertex from source
4. Initialize distance[source] = 0 and visited[source] = true
5. While not all vertices have been visited yet, or loop V-1 times
   a. Find the unvisited vertex with minimum distance to any of the visited vertices
   b. Mark it as visited
   c. Update the distance matrix with the distances from the newly added vertex: if distance[vertex] + adj[vertex][current] < distance[current], then update.