A looped tree G = (V, E) is an edge-weighted directed graph built from some (dir

Question

A looped tree G = (V, E) is an edge-weighted directed graph built from some (directed) binary tree T on V rooted at some node r V, by adding an edge from every leaf in T back to r (e.g., if T was a long directed path, the looped tree G would be a cycle). Assume that the vertices are labeled from 1, . . ., n, with the root r having label 1, and the edges are given in the form of an adjacency list, along with the corresponding edge weights. Moreover, assume that all the edge weights are non-negative.

Your goal in this problem be to develop a faster-than-Dijkstra single-source shortest-path algorithm computing all shortest distances d[v] from a given input node u V to all other nodes v of G. You will do it by solving the following sub-problems:

(1) Show that the number of edges in G is O(n).

(2) Compute the running time of Dijkstra’s algorithm to compute the shortest distance d[v] from a given vertex u to all v V.

(3) Modify the BFS algorithm from the lecture appropriately to give an O(n) algorithm that computes for all v V the shortest distance c[v] from the root r to v.

(4) Give an O(n) algorithm that computes the shortest distance from u to the root r, for the given source vertex u. (Hint: Think of recursion, but make sure you terminate, and fast!)

(5) Let T = (V, E') be the original rooted tree you started from (before adding the edges from the leaves of T to r). Give an O(n) algorithm to compute the shortest distance b[v] from u to v in T (not G), for all v V.

(6) In G, express (with proof) the shortest distance d[v] from u to v in terms of b[v], c[v], and . Use this expression to obtain an algorithm to compute d[v] for all v V with running time asymptotically faster than Dijkstra’s algorithm.

Explanation / Answer

(1) Show that the number of edges in G is O(n).

Explore all the vertices in ascending order of distance from s: (Assume the nodes are at different lengths from sand that no edge has zero distance)

Initialize for all nodes v: dist(s, v) =

Initialize S = , d0(s, s) = 0

for i = 1 to |V| do

//S contains the i-1 nearest nodes to s

//d’(s,u) is shortest path length from u to s specifically utilizing S as intermediate nodes

Assume v be such that d’(s,v) = minuVS d’(s,u)

dist(s, v) = d0(s, v)

S = S {v}

for each node u in V S

calculate d’(s,u) = minaS (dist(s, a) + `(a, u))

Running time: O(n * (n + m)) time.

In each n outer iterations, d0(s, u) for each u by scanning every edge out of nodes in S givesO(m + n) time/iteration.

(2) Compute the running time of Dijkstra’s algorithm to compute the shortest distance d[v] from a given vertex u to v for all v V.

Dijkstra’s algorithm implementation

// An algorithm to calculate the shortest path distances from u, and hold them in P

static void Dijkstra(Graph G, int s, int[] P) {

for (int i=0; i<G.n(); i++) // Start(initialize)

     P[i] = Integer. HIGH_VALUE;

     P[s] = 0;

for (int i=0; i<G.n(); i++) { // Process and get the vertices

int v = minVertex(G, P); // Get succeeding-closest vertex

G.setMark(v, VISITED);

if (D[v] == Integer. HIGH_VALUE) return; // Vertex unreachable

for (int w = G.first(v); w <G.n(); w = G.next(v, w))

if (P[w] > (P[v] + G.weight(v, w)))

     P[w] = P[v] + G.weight(v, w);

}

}

(3) Modify the BFS algorithm appropriately to give an O(n) algorithm to compute the shortest distance c[v] from the root r to v, for all v V.

Let G be the directed graph with non-negative edge lengths.

Assume that dist(s, v) denotes the smallest route distance from s to v. Consequently if s = v0 v1 v2 . . . vk is a shortest route from s to vk , therefore, for 1 i < k:

s = v0 v1 v2 . . . vi is the shortest route from s to vi

dist(s, vi) dist(s, vk)

It follows that for some i < k there is a path P0 from s to vi of length precisely less than that of s = v0 v1 . . . vi. Then P0 linked with vi vi+1 . . . vk holds a precisely shorter route to vk than s = v0 v1 . . . vk

Given the directed graph G = (V, E) and node s V

Represent all vertices as unexplored and for every v set dist(v) =

Initialize search tree T to be empty

Denote vertex s as explored and set dist(s) = 0

Then set Q to be the empty queue

enq(s)

while Q is nonempty do

u = deq(Q)

for every vertex v Adj(u) do

if v is not explored do

add edge (u, v) to T

Mark v as explored, enq(v)

and set dist(v) = dist(u) + 1

The BFS runs in O(n + m) time.

(4) Give an O(n) algorithm that computes the shortest distance from u to the root r, for the given source vertex u. (Hint: Think of recursion, but make sure you terminate, and fast!)

static void Primalgorithm(Graph G, int s, int[] P, int[] V) {

for (int i=0; i<G.n(); i++) // Start(initialize)

      P[i] = Integer.HIGH_VALUE;

      P[s] = 0;

for (int i=0; i<G.n(); i++) { // Process and get the vertices

int v = minVertex(G, P);

G.setMark(v, VISITED);

if (v != s) AddEdgetoMST(V[v], v);

if (P[v] == Integer. HIGH_VALUE) return; // Vertex unreachable

for (int w = G.first(v); w <G.n(); w = G.next(v, w))

if (P[w] >G.weight(v, w)) {

     P[w] = G.weight(v, w);

     V[w] = v;}

          }

      }

(5) Let T = (V, E) be the original rooted tree you started from (before adding the edges from the leaves of T to r). Give an O(n) algorithm to compute the shortest distance b [v] from u to v in T (not G), for all v V.

To reduce many computations during the algorithm, every vertex v V(G) is corresponds to a
function d’(v) which denotes an upper bound on dist(r,v), and to a vertex p(v) which represents the potential parent of v in the tree. In each phase there is

d’(v) = dist(r,v) if v V(Ti)
d’(v) = min{dist(r,u)+ w(uv)} if v V(Ti)

Initialize d’(r) := 0 and d’(v) := + if v != r. T0is the tree comprising of the single vertex
r, u0 := r and i := 0.
For any v V(Ti), if d’(ui)+ w(uiv) d’(v), then d’(v) := d’(ui)+ w(uiv) and p(v) := ui.
Calculatemin{ d’(v) | v V(Ti)}. Assumeui+1 is a vertex for which this minimum is reached. Let Ti+1 be the tree obtained by adding the vertex ui+1 and the edge p(ui+1)ui+1.
If i = |V | 1, return Ti, else i :=i+ 1.

(6) Express (with proof) the shortest distance d[v] from u to v in terms of b[v], c[v], and . Use this expression to obtain an algorithm to compute d[v] for all v V with running time asymptotically faster than the Dijkstra’s algorithm

Bellman-Ford algorithm chooses the shortest path based on the order of relaxations.

Shortest paths exist if there exists no negative weight cycle.Make the assumption that the graph isstrongly connected(it is possible to move from any node to any other node in either direction)

Letd (u, v, k) be the length of the shortest path u vwith at most k edges

Run a DP on d (u, v, k).

Recurrence: A path with at most k edges is an enhancement on a path of at most k – 1 edges if there exists a shorter path reaching a succeeding node in at most k 1 edges that moves on to reach this node through the kth edge.

Hence

d (u, v, k) = min {d (u, v, k 1)

minzV {d (u, z, k 1) + w (z, v)}

Bellman-Ford algorithm

D[y][0] = {0 if u = v

otherwise

For k from 1 to n-1:

For z V:

D[z][k] := D[z][k-1]

Forij an edge:

D[j][k] := min( D[j][k], D[i][k-1] + w(i,j) )

The Complexity for this algorithm is given by O (n (n + m)) = O (nm)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.