Let G V E be a directed graph with weighted edges edge weig

Let G = (V, E) be a directed graph with weighted edges; edge weights could be positive, negative, or zero. How could we delete an arbitrary vertex v from this graph, without changing the shortest path distance between any other pair of vertices? Describe an algorithm that constructs a directed graph G\' = (V\', E\')with weighted edges, where V\' = V/{v}, and the shortest-path distance between any two nodes in H is equal to the shortest-path distance between the same two nodes in G, in O(V^2) time. Now suppose we have already computed all shortest-path distances in G\'. Describe an algorithm to compute the shortest-path distances from v to every other vertex, and from every other vertex to v, in the original graph G, in O(V^2) time. Combine parts (a) and (b) into another all-pairs shortest path algorithm that runs in O(V^3) time. (The resulting algorithm is not the same as Floyd-Warshall!)

Solution

Ans a

If we are deleting an arbitrary vertex from the graph so as vertex v is associated with the cost c(v) which is possibly positive, negative or zero. So we can define a method

                w 0 (uv) = c(u) + w(uv) c(v)

For every exit we have to pay cost.

We can construct a directed graph G’=(V’,E’) with weighted edges where V’=V/{v}

We can user the Johnson’s Algorithm

JOHNSONAPSP(V,E,w)

Create a new vertex s

For every vertex v

W(s->v)<-0

W(v->s)<-infinity

Dist[s,.]<-SHIMBEL(V,E,w,s)

If SHIMBLE found a negative cycle

Fail gracefully

For every edge (u,v)€E

W’(u->v)<-dist[s,u]+w(u->v)-dist[s,v]

For every vertex u

dist [u,.]<-DIJKSTRA(V,E,w’,u)

for every vertex v

dist[u,v]<-dist[u,v]-dist[s,u]+dist[s,v]

Ans b

For a given graph source vertex , Dijkstra algorithm finds the path with lowest cost from the vertex to every other vertex.

In this algorithm we have following :

function Dijkstra(Graph,Source)

                for each vertex v in graph: //initialization

                dist[v]:=infinity //unknown distance function from source to v

                previous[v]:=undefined //previous node in optimal path from source

                dist[source]:=0

                Q:=the set of all nodes in graph

                While Q is not empty:

                                U:=vertex in Q with smallest dist[]

                                If dist[u]=infinity:

                                Break

                Remove u from Q

                For each neighbour v of u //where v has not been removed from Q

                                Alt:=dist[u]+dist_between(u,v)

                                If alt<dist[v]

                                                Dist[v]:=alt

                                                Previous[v]:=u

                Return previous[]

Anc C

Solution of all-pairs shortest path problem that uses dynamic programming instead of single source-algorithm. For dense graph where E =(V2),the dynamic programming approach eventually leads to O(V3)

Algorithm:

For all vertices u

                For all vertices v

                                If(u=v)

                                                Dist[u,v,0]<-0

                                Else

                                                Dist[u,v,0]<-

For k<-1 to v-1

                For all vertices u

                Dist[u,u,k]<-0

                For all vertices v u

                                Dist[u,v,k]<-

                                For all edges x->v

                                                If dist[u,v,k]>dist[u,x,k-1]+w[x->v]

                                                                Dist[u,v,k]<-dist[u,x,k-1]+w(x->v)