Design a system that finds the shortest paths between various location

Back to the 2024 paper

Module 3: Graph and Tree Algorithms

20247m

Design a system that finds the shortest paths between various locations in a city. The locations and roads are represented using a graph. What algorithm would you use if:
(i) All roads have equal length
(ii) Roads have varying lengths, but no negative lengths
(iii) Some roads have negative lengths
Justify your choices with suitable algorithms and reasoning.

Search Google Ask AI

Similar questions

Design & Analysis of AlgorithmsAn all-pairs shortest-paths problem is efficiently solved using: - (i) Dijkstra's algorithm - (ii) Bellman-Ford algorithm - (iii) Kruskal algorithm - (iv) Floyd-Warshall algorithm20192m Design and Analysis of Algorithms Which of the following algorithm solves the All Pair Shortest Path problem (i) Dijkstra's (ii) Floyd's Warshall's (iii) Prim's (iv) Kruskal's20222m Design & Analysis of AlgorithmsDijkstra's algorithm is used to solve ______ problems? - (i) Single source shortest path - (ii) All pair shortest path - (iii) Sorting - (iv) Searching20242m Design and Analysis of Algorithms Consider a TSP with 4 cities A, B, C, D and the following distance matrix: | | A | B | C | D | |---|---|---|---|---| | A | 0 | 10 | 15 | 20 | | B | 10 | 0 | 35 | 25 | | C | 15 | 35 | 0 | 30 | | D | 20 | 25 | 30 | 0 | Answer the following: (i) Use the branch-and-bound algorithm to find the shortest possible route that visits all cities exactly once and returns to the starting city. (ii) Show the branching steps and calculate lower bounds for each partial solution. (iii) Identify how the bounding helps prune the search tree.20247m

PreviousAnswer the following: (i) Compare and contrast the BFS and DFS traversal techniques in terms of their algorithmic approach, time complexity, data structures used, and typical applications. (ii) Give examples where one is preferred over the other.NextA graph with five nodes is represented using the adjacency list as follows: | | | | | | |---|---|---|---|---| | A | -> | B (10) | C (3) | | | B | -> | C (1) | D (5) | | | C | -> | B (4) | D (8) | E (2) | | D | -> | E (7) | | | | E | -> | D (9) | | | Answer the following: (i) Draw the graph for the above adjacency list. (ii) Write the algorithm for the Breadth-First Traversal (BFS). (iii) Show the BFS traversal of the graph with the starting node as A.