Assignment 2 no late homework would be accepted 1 (Exercise XXXXXXXXXXLet G = (V,E) be a weighted, directed graph with nonnegaive weight function w : E → {0, 1, ...,W} for some nonnegative integer W ....

Assignment – 2
1. According to the Dijkstra’s algorithm where Q depicts queue and S signifies a state, the following are the sequential steps:
a. Till the Q is not empty, we will follow up the iteration, remove node signified with v, which is not present at all in S from Q having at least distance (v). Initially initialize the state, s to 0
b. When we visit a node, we add that node v to S.
c. Update the values of distance of all adjacent nodes of the given node v and for every new upcoming adjacent node called as u.
d. Check the following distance condition:
If dist(v) + weight(u,y) < dist(u), then do the updating of new distance u which should be minimum else no need of updating and iteration will keep on going till all nodes are visited or it is terminated.
    The time complexity is on the execution time of Min-Priority queue used as a data structure here. Adjacent vertices which are quite close to the source vertex get evaluated first. Each node or vertex will definitely have its weight W. Highest value counted for the longest path of any graph is given up by (v – 1) * W. So in the queue, we can process the vertices which are available, here dist (v) will suggest us the shortest path from source to any other vertex v.
Taking into consideration that queue here has (v – 1 ) * W buckets, from these buckets , we can extract node v from the bucket d[v]. From source to vertex v, the value ranges between 1 and ( v – 1) * W as nodes can be found in buckets 1,2…. ( v – 1 ) * W. Now, for a start, we have initialized from the bucket[0] where start is given by 0 or S and this keeps on going till all the nodes are discovered.
So now, we will be having buckets from 0 to (v -1) * W. After initializing all nodes with that, we will go on traversing it, and when the bucket is found which is not empty, its first vertex will be taken out and the rest of its adjacent nodes will be reset. So from this step, we can count that the time complexity till O(WV) and when we are traversing through all edges given by E, as the vertices will be connected through edges, so we can count out that O(WV + E) as the time complexity.
Given D as Dijkstra’s algorithm with G as graph, W as weight, S as state
D (G, W, S)
1. Initialize the (G, S)
2. Initialize S as empty, S { }
3. Initialize Q where Q V[G]
4. Iterate through the given loop
While Q != empty
{
    Execution of the code till Q = { }
}
Let u min( Q)
Let S S U {u}
for each vertex v which belongs to adj[u]
    reset(u, v, W) // compute the weight
2. Suppose the weighted directed graph is given by G = (V, E) where weights are depicted with
w: E → R and V depicts the collection of vertices and E gives edges list.
So for each edge given as (u, v) belonging to E, there is a shortest path from the source vertex s which has edge given by (u, v) and there is a presence of one more shortest path which does not contain the same edge (u, v) in its traversed path.
Basically as we know that graphs in which we have directed edges with arrow symbols which predicts the direction of movement from one vertex to another and there are other type of graphs which does not have these symbols called as undirected graphs.
The given property mentioned above cannot be valid for the acyclic graphs as they comprised of unique edges connecting one vertex to another
So, coming to the cyclic graphs, we can have a look over the given example
Lets suppose Q → T , we will find out the path from Q to R vertex so in the given graph we have
Two ways
1. Q → R , we can reach R through Q → T ...