Consider m-Graph

Coloring Problem for an input of graph of n vertices. In backtracking, the

total number of nodes in State Space Tree for m=4 and n=5 are

In the given graph, identify the shortest path having minimum cost to reach vertex ‘e’ if ‘a’ is the source vertex.

You are given a directed graph

G=(V,E) with edge weights that may be negative but

1. A new

   vertex s is added to the graph, connected to every vertex v∈V

   with an edge of weight 0.

2. A

   shortest-path algorithm is run from sss to compute a potential function

   h(v) for each v∈V

3. 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)

1. 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?

A monitor is a module that encapsulates ______