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.