1. Draw the graph G: 2. Apply Dijkstra’s Algorithm and find out the Shortest Path 3. Apply Bellman-Ford Algorithm and find out the Shortest Path
In these days, drones and robots are being used commercially to deliver the packages to a
specific location. A departmental store needs to develop an application so that when the source
and destination is known, the robot/drone moves in the ordered direction by following the shortest path to keep delivering the package in a minimum amount of time. Initially store has
identified few areas and a directed weighted graph G is made of with different routes.
Here G = (V, E), where V is the set of locations as V = {H, A, B, C, D, E, F} and H is the source
node. E is the set of routes with weights (distances), shown in table with respective edges.
Edge HA HB AC CF BD DF HE BE EC FE
Weight 6 7 3 8 2 9 X 1 1 Y
HERE X=10 for EVEN roll# and X=5 for ODD roll# and Y= (roll# mod X) + 5
Hint: Suppose roll# is 2018-CS-312, since 312 is even, X=10 and Y= (312 mod 10) + 5 = (2) + 5
= 7
You will need to cover following tasks
1. Draw the graph G:
2. Apply Dijkstra’s
3. Apply Bellman-Ford Algorithm and find out the Shortest Path
4. Compare the two algorithm on the basis of efficiency and time complexity
5. If it is supposed that value of Y is negative, what would be the impact of this on both
algorithm?
Step by step
Solved in 2 steps with 4 images
