Let G=(V,E) be a weighted, directed graph with weight functions as w : E-> {1,2,

ID: 3615374 • Letter: L

Question

Let G=(V,E) be a weighted, directed graph with weight functions as w : E-> {1,2,3...W} for some positive integer W, and assume that no two vertices have the same shortest-path weights from source vertex s.Now suppose that we define an unweighted, directed graph G'=(V U V',E') by replacing each edge (u,v) ephsilon E with w(u,v) unit-weight in series.How many vertices does G' have? Now suppose that we run a breadth- first search on G'. Show that the order in which vertices in V are colored black in the breadth - first search of G' is the same as the order in which the vertices of V are extracted from from priority queue in line 5 of DIJKSTRA when run on G.

Explanation / Answer

According to the questions, for each edge with weight k (kbelongs to {2, 3, ..., W} ), it needs to split into k unit edge,and k-1 additional vertices are added to the V'. So 1 + 2 + ... +W-1 vertices are added, that is W*(W-1)/2. Thus, G' containsW*(W-1)/2 + |V| vertices. Breadth-first search (BFS) on G' will colorvertices level by level: first color the vertices which are 1step from source vertex s, then color those 2-step from s, and soon. So for any vertex u that is i steps from s, and any vertexv that is j steps from s, and i < j, then u must be coloredprior to v. Since no two vertices have the same shortest-pathweights from source vertex s, so for any vertex in V of G', thedistance from s to that vertex is unique. Thus, for any pairof vertices u and v in V, we can dertermine the ordre they arecolored by their distance to s based on the rule above. In Dijkstra, the vertices of V are extracted from the priorityqueue in the increasing order of the distance (weight) of theshortest-path from source vertex to that vertex. (Since no twovertices have the same shortest-path weights from source vertex s,so there is no tie and the order is fixed). i.e.: forany vertex u that has shortest-path weights i from s, and anyvertex v that has shortest-path weights j from s, and i < j,then u must be colored prior to v. That means the order in which vertices in V are colored blackin the BFS of G' is the same as the order in which the vertices ofV are extracted from from priority queue of Dijkstra when runon G.

Navigate

Let G=(V,E) be a connected graph and v be a node of G. The eccentricity e(v) of

Let G?L(R^n;R^n) be the subset of invertible linear transformations. a) For H?L(

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

Let G=(V,E) be a weighted, directed graph with weight functions as w : E-> {1,2,

Question

Explanation / Answer

Related Questions

Navigate