Scribd
Upload
54 views5 pages

Graph Theory Assignment 4

The document contains assignments on graph theory algorithms for a 7th semester BTech student at Central Institute of Technology in Kokrajhar, India. It includes questions about explaining the Dijkstra and Bellman-Ford algorithms, analyzing their time complexities, and describing scenarios where each algorithm does not work. The student provided detailed answers explaining the greedy approach of Dijkstra's algorithm, its O(V^2) or O(ElogV) time complexity depending on the graph representation. For Bellman-Ford, the student explained its ability to handle negative edge weights, the relaxation principle it uses, its O(V*E) time complexity, and that it fails only if there is a negative cycle reachable from the source

Uploaded by

gixi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
54 views5 pages

Graph Theory Assignment 4

The document contains assignments on graph theory algorithms for a 7th semester BTech student at Central Institute of Technology in Kokrajhar, India. It includes questions about explaining the Dijkstra and Bellman-Ford algorithms, analyzing their time complexities, and describing scenarios where each algorithm does not work. The student provided detailed answers explaining the greedy approach of Dijkstra's algorithm, its O(V^2) or O(ElogV) time complexity depending on the graph representation. For Bellman-Ford, the student explained its ability to handle negative edge weights, the relaxation principle it uses, its O(V*E) time complexity, and that it fails only if there is a negative cycle reachable from the source

Uploaded by

gixi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 5

CENTRAL INSTITUTE OF TECHNOLOGY, KOKRAJHAR

Department of Information Technology

Program: Assignment on Graph Theory


Course Code: IT 717

Semester: 7th

Nabajyoti Dewri
GAU-C-17/257
Information Technology(IT)
B.Tech 7th sem
1. Explain the Dijkstra algorithm and analyze its complexity.
Ans:
It is a greedy algorithm that solves the single-source shortest path problem for a
directed graph G = (V, E) with nonnegative edge weights, i.e., w (u, v) ≥ 0 for each edge
(u, v) ∈ E.

Dijkstra's Algorithm maintains a set S of vertices whose final shortest - path weights
from the source s have already been determined. That's for all vertices v ∈ S; we have d
[v] = δ (s, v). The algorithm repeatedly selects the vertex u ∈ V - S with the minimum
shortest - path estimate, inserts u into S and relaxes all edges leaving u.

Because it always chooses the "lightest" or "closest" vertex in V - S to insert into set S, it
is called as the greedy strategy.

Dijkstra's Algorithm (G, w, s)


1. INITIALIZE - SINGLE - SOURCE (G, s)
2. S←∅
3. Q←V [G]
4. while Q ≠ ∅
5. do u ← EXTRACT - MIN (Q)
6. S ← S ∪ {u}
7. for each vertex v ∈ Adj [u]
8. do RELAX (u, v, w)
Time Complexity Analysis-
 
Case-01:
 
This case is valid when-

 The given graph G is represented as an adjacency matrix.


 Priority queue Q is represented as an unordered list.
 
Here,

 A[i,j] stores the information about edge (i,j).


 Time taken for selecting i with the smallest dist is O (V).
 For each neighbor of i, time taken for updating dist[j] is O (1) and there will be
maximum V neighbors.
 Time taken for each iteration of the loop is O (V) and one vertex is deleted from Q.
 Thus, total time complexity becomes O(V2).
 
Case-02:
 
This case is valid when-

 The given graph G is represented as an adjacency list.


 Priority queue Q is represented as a binary heap.
 
Here,

 With adjacency list representation, all vertices of the graph can be traversed using
BFS in O(V+E) time.
 In min heap, operations like extract-min and decrease-key value takes O (logV) time.
 So, overall time complexity becomes O(E+V) x O(logV) which is O((E + V) x logV) =
O(ElogV)
 This time complexity can be reduced to O (E+VlogV) using Fibonacci heap.

2. Explain the Bellman-Ford Algorithm and analyze its complexity.

Ans:

Solves single shortest path problem in which edge weight may be negative but no
negative cycle exists.

This algorithm works correctly when some of the edges of the directed graph G may have
negative weight. When there are no cycles of negative weight, then we can find out the
shortest path between source and destination.

It is slower than Dijkstra's Algorithm but more versatile, as it capable of handling some of
the negative weight edges.

This algorithm detects the negative cycle in a graph and reports their existence.

Based on the "Principle of Relaxation" in which more accurate values gradually recovered
an approximation to the proper distance by until eventually reaching the optimum
solution.

Given a weighted directed graph G = (V, E) with source s and weight function w: E → R,
the Bellman-Ford algorithm returns a Boolean value indicating whether or not there is a
negative weight cycle that is attainable from the source. If there is such a cycle, the
algorithm produces the shortest paths and their weights. The algorithm returns TRUE if
and only if a graph contains no negative - weight cycles that are reachable from the
source.

Recurrence Relation

distk [u] = [min[distk-1 [u],min[ distk-1 [i]+cost [i,u]]] as i except u.

k → k is the source vertex


u → u is the destination vertex
i → no of edges to be scanned concerning a vertex.

BELLMAN -FORD (G, w, s)


1. INITIALIZE - SINGLE - SOURCE (G, s)
2. for i ← 1 to |V[G]| - 1
3. do for each edge (u, v) ∈ E [G]
4. do RELAX (u, v, w)
5. for each edge (u, v) ∈ E [G]
6. do if d [v] > d [u] + w (u, v)
7. then return FALSE.
8. return TRUE.
Time Complexity Analysis-
Time complexity of Bellman-Ford algorithm is Θ (|V||E|) where |V| is number of
vertices and |E| is number of edges. If the graph is complete, the value of |
E| becomes Θ (|V|2). So overall time complexity becomes Θ (|V|3). And given here
is an n vertex. So, the answer ends up to be Θ (n3).

3. Describe the scenarios where Dijkstra algorithm does not work.


Ans: Dijkstra algorithm does not work with graphs having negative weight edges. The
below image is a classic example of Dijsktra algorithm being unsuccessful with negative
weight edges.

Dijkstra follows a simple rule if all edges have non negative weights, adding an edge will
never make the path smaller. That's why it follows the greedy strategy and picks up the
shortest path and in turn which turns out optimal.
Let's start with A.
A -> A will be marked as 0, everything else from A will be infinity.

In next turn
A -> B will be 1.
A -> D will be 99.
A -> C will be 0.

No changes will be there if you expand vertices B and C.

When you expand D that will change A -> B to -201.

Still A -> C is 0, when there is a shorter path from A -> D -> B -> C costing -200. Dijsktra
will not be able to find out this and it fails.

4. Describe the scenarios where Bellman-Ford Algorithm does not work.


Ans: If there are negative cycles (reachable from the source), Bellman-Ford Algorithm
can be considered to fail. The main problem with a negative cycle is that you can just
keep traversing it, reducing the cost of the path, thus there exists no finite shortest path to
some vertices (so it's arguable whether Bellman-Ford actually failed or not - it can detect
these cycles).

You might also like