// Dijkstra’s Algorithm for SSSP// Source = v0marked[v0] = true;for each vertex v != v0 {marked[v] = false;if v is adjacent to v0d[v] = length of edge v0->v;elsed[v] = infinity;}for (i = 0; i < n-1; i++) {min_w = first unmarked vertex;min_weight = d[min_w];for each vertex vif (!marked[v])if (d[v] <= min_weight) {min_w = v;min_weight = d[v];}marked[min_w] = true;for each vertex v adjacent to min_wif (!marked[v]) {new_est = min_weight + length of edge min_w->v;if (new_est < d[v])d[v] = new_est;}} // for1// Dijkstra’s Algorithm for SSSP that keeps track of pathsmarked[v0] = true;for each vertex v != v0 {marked[v] = false;p[v] = v0;if v is adjacent to v0d[v] = length of edge v0->v;elsed[v] = infinity;}for (i = 0; i < n-1; i++) {min_w = first unmarked vertex;min_weight = d[min_w];for each vertex vif (!marked[v])if (d[v] <= min_weight) {min_w = v;min_weight = d[v];}marked[min_w] = true;for each vertex v adjacent to min_wif (!marked[v]) {new_est = min_weight + length of edge min_w->v;if (new_est < d[v]) {d[v] = new_est;p[v] = min_w;}}} // for2// Dijkstra’s algorithm using a priority queuemarked[v0] = true;d[v0] = 0;p[v0] = v0;for each vertex v != v0 do {marked[v] = false;p[v] = v0;if (v is adjacent to v0)d[v] = length of edge v0->v;elsed[v] = infinity;}buildHeap(v0, d, loc_in_heap, heap);for (i = 0; i < n-1; i++) {(min_w, min_weight) = heap.deleteMin(loc_in_heap);marked[min_w] = true;loc_in_heap[min_w] = NOT_IN_HEAP;for each vertex v adjacent to min_w doif (!marked[v]) {new_est = d[min_w] + length of edge min_w->v;if (new_est < d[v]) {d[v] = new_est;heap.update(v, new_est,
View Full Document
Unlocking...