EXPERT ANSWER
1.1
The part of Kruskal’s algorithm that make a disjoint set of each vertex of a graph is given as follows:
For each vertex v in graph G
Make-Set(v)Make-Set(v): Make-Set(v) makes a disjoint set for vertex v such that the set contains only v in it.
Thus, the above for loop creates a disjoint forest of n trees where n is the total number of vertex in graph G. Each tree contains only one vertex of graph G.
Forest: A forest is a acyclic, disconnected, and undirected graph.
The edges of a graph are added to the disjoint forest in increasing order of their weight if its both ends are in different trees. Thus the number of edges in the forest created by Make_Set() for each vertex of a graph does not remain constant.
The proof of the above statement is given by considering the following weighted undirected graph G
Adding edges in increasing order one by one to the forest:
- After creating the disjoint forest, Kruskal’s algorithm selects each edge in the increasing order of their weight.
- The edge is added to the forest if both ends of the edge do not belong to the same tree. In other words, the edge is added if it connects two different trees in the forest.
The order of the edges of the graph G in the increasing order of their weight is as follows:{(V1,V2},(V3,V4),(V2,V5),(V1,V3),(V2,V4),(V4,V5)}Select edge (v1, v2):
Since edge (v1, v2) connects two distinct trees in the forest, add this to the forest.Select next edge (v3, v4):
Since edge (v3, v4) connects two distinct trees {v3} and {v4} in the forest, add this to the forest.Select next edge (v2, v5):
Since edge (v2, v5) connects two distinct trees {v1, v2} and {v5} in the forest, add this to the forest.
Select next edge (v1, v3):
Since edge (v1, v3) connects two distinct trees {v1, v2, v5} and {v3, v4} in the forest, add this to the forest.Select next edge (v2, v4):
Since both ends of edge (v2, v4): {v2} and {v4} are in the same tree in the forest, the edge is not added in the tree. (Or adding this edge to the forest creates a cycle whose start vertex and end vertex are same, so the edge is discarded).
Select next edge (v4, v5):
Since both ends of edge (v4, v5): {v4} and {v5} are in the same tree in the forest, the edge is not added in the tree.
An edge (u, v) with the least possible weight is selected from the graph and added to the forest to connect two distinct trees, one contains vertex {u} and another vertex {v}.
Since edges are selected one by one and added to the forest if both ends of an edge are in different trees of the forest, the number of edges in the disjoint forest increases by 1 until the forest becomes a tree ( A connected acyclic undirected graph).
Total number of edges that connects all trees in a disjoint forest of n vertices is always (n – 1) where n is the number of the vertices in a graph.
Hence, it is proved that the number of edges in the disjoint forest created by calling Make-Set( ) method on each vertex of the graph does not remain constant until the end of the algorithm.
1.2Dijkstra’s Algorithm Dijkstro’s algorithm in that a vertex is marked as “closed” and out of the open sel the algorithm found the shortest path to it, and will never have to develop this node again. it assumes the path developed to this path is the shortest. – But with negative weights – it not true. It always terminates after El relaxations and VI+IE! priority queue operations, but may produce incorrect results. for example
V = {A, B, C}; E = {CA,C,2), CA,B,5)} Dijkstra from A will first develop c, and will later fail to find A-> B-> C
1.3:
Dijkstra’s algorithm is given as follows:
Initialize distance d of each vertex from a source vertex ∞.
Initialize the parent of each vertex NIL.
Set distance d of the source vertex s to 0.
Take a set S that contains vertices whose shortest path(distance) from the source vertex has already been computed.
Initialize minimum-priority queue Q for each vertex v with the value of d.v
Run a while loop until Q is not empty:
Select the minimum distance u vertex from Q.
Add vertex u in set S.
Relax each adjacent vertex of vertex u that is not in S.Relax a vertex v:
if distance of vertex v > distance of vertex u + weight of edge (u, v),
set the distance of vertex v = distance of vertex u + weight of edge (u, v)
and the parent of vertex v = u
Find the shortest path(distance) of each vertex from the source vertex using Dijkstra algorithm given above.
- The shortest distance of vertex s is 0.
- The shortest distance of vertex x from source vertex s is 1.
- The shortest distance of vertex v via x is -3.
Thus, Dijkstra algorithm works well with the negative-weight edges if it does not contain a negative-weight cycle.
Dijkstra algorithm always consider a graph with non-negative edges. Since after finding a shortest path from source vertex to any vertex x, the vertex x is not reconsidered.
Add an edge (s, v) to the graph given in the fifth step with a positive weight in such a way that it creates a negative weight cycle.
The graph after adding edge is given as follows:
A cycle in the graph is said to be a negative weight cycle if sum of all the edges of the cycle is less than 0.
Here the graph has cycle <s, x, v> whose sum of the edges is less than 0.
Hence, cycle <s, x, v> is a negative-weight cycle.
The shortest path from s to x is 1.
There are infinitively many paths to reach from s to vertex x such as {s, x}, {s, x, v, s, x}, {s, x, v, s, x, v, s, x} and so on.
The weight of path {s, x} is 1.The weight of path {s, x, v, s, x} is 0.The weight of path {{s, x, v, s, x, v, s, x} is -1.
It is seen that every time the weight of the shortest path from s to x decreases by -1 as number of cycles in the path increases.Thus, the weight of the shortest path from s to x is .
Since vertex v is reachable from vertex x, its shortest path from s will also be .Hence, when a graph contains a negative-weight cycle, a shortest path for a vertex from a source vertex is not defined.
Find the shortest path(distance) of each vertex from the source vertex using Dijkstra algorithm given step fourth. Since the shortest distance of vertex s is 0, add s to set S and find the distance of x and v via s. Hence, vertex S is visited. and .
Select unvisited vertex whose distance is the shortest.
Since the shortest distance of vertex x is 1, add x to set S and find the distance of v via x. Hence, vertex x is visited.. Select unvisited vertex whose distance is the shortest.Since vertex v is the last vertex that is unvisited and here the execution of the algorithm gets completed. Using Dijkstra algorithm:
- The shortest distance of vertex x from source vertex s is 1.
- The shortest distance of vertex v via x is -3.
Since the shortest path computed by the algorithm is not correct, Dijkstra’s algorithm fails to compute the correct shortest path of the vertices of a graph with negative-weight cycle.
Since in Dijkstra’s algorithm once the shortest path of a vertex from a source vertex is computed or a vertex is visited, the shortest path of the vertex is not considered to be updated later in the algorithm. Thus, the algorithm is not able to detect the negative-weight cycle and the correct shortest path to reach to the vertices from the source vertex.
Hence, it is proved that Dijkstra’s algorithm does not return a correct result when there is a negative-weight cycle in the graph.
1.4:
The first step of Dijkstra’s algorithm is to initialize the distance of a source vertex to 0 and all other vertices from the source vertex to.Consider a graph given as follows:
represents that the path of a vertex from the source vertex s is not defined yet.Relax an edge (a, b):
An edge is relaxed by using the following steps:
Check if the weight of the path to reach vertex b via vertex a is less than the previously computed distance of vertex b.When an edge (a, b) is relaxed, the distance of vertex b is updated if the distance of vertex b via the vertex a is less than its previously computed distance. Thus, relaxing an edge helps to find the path of each vertex from the source.
In the graph, the source vertex s has three paths to x.
Consider the first path is { s, v1, v2, v3, x}.
The proof of the statement “Edge (v1, v2) is relaxed before edge (v2, v3) in the path { s, v1, v2, v3, x}” is given by considering that edge (v2, v3) is relaxed before edge (v1, v2).
If edge (v1, v2) is not relaxed then the distance of vertex v2 from the source vertex is not defined and it is ∞.Since vertex v3 can be reached from only vertex v2, the distance of vertex v3 via vertex v2 is also ∞ and thus the distance of x via vertex v3 is also ∞.Thus, if edge (v1, v2) is not relaxed then there is no path defined from source vertex s to vertex x via vertices v1 and v2. That contradicts the statement that there is a path from the source vertex s to vertex x.
Hence, the statement “ Edge (v2, v3) is relaxed before edge (v1, v2)” is wrong.
A path from the source vertex s to any vertex x is a trail of the edges in which each edge is relaxed in the order of the edges starting from the source vertex such as (s, v1), (v1, v2), (v2, v3), and (v3, x).
Hence, it is proved that if there is a path <s, v1, v2, …..vk, x> from source vertex s to any vertex then every edge (vi, vi+1) is relaxed before edge (vj , vj+1) where 0 <= i < j <= k+1.