You are given a directed graph
G=(V,E) with edge weights that may be negative but no negative-weight cycles .
An algorithm is applied to compute the shortest paths between all pairs of
vertices , and it proceeds as follows:

A new
vertex s is added to the graph, connected to every vertex v∈V
with an edge of weight 0.
A
shortest-path algorithm is run from sss to compute a potential function
h(v) for each v∈V
Each edge weight w(u,v)w(u,
v)w(u,v) is reweighted as:

w′(u,v)=w(u,v)+h(u)−h(v)w'(u, v) = w(u, v) + h(u) -
h(v)w′(u,v)=w(u,v)+h(u)−h(v)

Dijkstra’s algorithm is run from
each vertex in the reweighted graph to compute shortest paths.

What is the main purpose of reweighting the edges using the
function h?

Question

You are given a directed graph
G=(V,E) with edge weights that may be negative but  no negative-weight cycles .
An algorithm is applied to compute the shortest paths between  all pairs of
vertices , and it proceeds as follows:

A new
     vertex s is added to the graph, connected to every vertex v∈V
     with an edge of weight 0. 
  A
     shortest-path algorithm is run from sss to compute a potential function
     h(v) for each v∈V 
  Each edge weight w(u,v)w(u,
     v)w(u,v) is reweighted as:

w′(u,v)=w(u,v)+h(u)−h(v)w'(u, v) = w(u, v) + h(u) -
h(v)w′(u,v)=w(u,v)+h(u)−h(v)

Dijkstra’s algorithm is run from
     each vertex in the reweighted graph to compute shortest paths.

What is the  main purpose of reweighting the edges  using the
function h?

Accepted Answer

To make Dijkstra’s algorithm applicable by
ensuring all edge weights are non-negative

Answer

To eliminate all negative-weight edges.

Answer

To ensure that the graph becomes undirected.

Answer

To improve the accuracy of Dijkstra’s algorithm
on negative-weight edges.

Crowdly

You are given a directed graph G=(V,E) with edge weights that may be negative b...

Want instant access to all verified answers on moodle.spit.ac.in?