Lecture 29 - 04/03

DFS vs. BFS, Shortest Paths

Shortest paths and Djikstra's Algorithm

public DijkstraSP(Graph G, int s) {
distTo = new double[G.V()];
DirectedEdge[] edgeTo = new DirectedEdge[G.V()];
distTo[s] = 0;
// Initialize cumulative distance to all non-start nodes
setAllDistancesToInfinityExceptS(distTo);
PQ<Integer> fringe = new PQ<>();
insertAllVertices(fringe);
// Relax vertices in order of distance from s
while (!fringe.isEmpty()) {
int v = fringe.delMin();
for (DirectedEdge e : G.adj(v)) {
relax(e);
}
}
}
private void relax(DirectedEdge e) {
int v = e.from();
int w = e.to();
// If edge is better than current
// Note: distTo[w] is initialized to infinity
if (distTo[w] > distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
// If the vertex w is still in the fringe, update its priority
if (fringe.contains(w)) {
fringe.decreasePriority(w, distTo[w])
}
}
}

Djikstra Runtime Analysis

A* Algorithm introduction

Extra: Look up Iterative DFS Algorithm