Exercise # 2: Modify getShortestPath (graph, from, to) function so that if there is more thanone minimum path from source node to destination node, it gives you the one with the minimumnumber of edges.Example 1:InputGraph: Adjacency list of the following graph.6.4From: ATo: For B[(A, F)]That is, the distance from A to Fis 10 both through the following pathA>D>F,AD>c>G>FOutputthe correct answer is AD>F((A, B)That is, the distance from A to B is 7 both through the following pathsA>B,AD>c>Bthe correct answer is AB

Program Code: import sys import heapq class Edge(object): def __init__(self, weight, startVertex,…

Exercise # 2: Modify getShortestPath (graph, from, to) function so that if there is more than one minimum path from source node to destination node, it gives you the one with the minimum number of edges.

Exercise # 2: Modify getShortestPath (graph, from, to) function so that if there is more than one minimum path from source node to destination node, it gives you the one with the minimum number of edges.

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter17: Linked Lists

Section: Chapter Questions

Problem 5SA

See similar textbooks

Similar questions

Exercise # 2 - Detecting Cycle between List of N Airports The following graph is an example from Rosen (2011). It shows the flights and distances between some of the major airports in the United States. Dallas 200 1300 200 Austin Washington Denver 1400 Atlanta 160 800 800 Chicago Houston Write a function that takes a list of N airports and checks if they form a cycle of size N. {A cycle is a directed path that starts and ends at the same vertex. Before writing code, make sure you can identify cycles yourself} >> check_cycles (G, ['Austin','Houston', 'Atlanta','Washington','Dallas'l) Yes >>> check_cycles (G, ['Austin', 'Houston','Atlanta','Washington']) No 600 600 780 0000 000L 006
In this project, you will develop algorithms that find road routes through the bridges to travel between islands. The input is a text file containing data about the given map. Each file begins with the number of rows and columns in the map considered as maximum latitudes and maximum longitudes respectively on the map. The character "X" in the file represents the water that means if a cell contains "X" then the traveler is not allowed to occupy that cell as this car is not drivable on water. The character "0" in the file represents the road connected island. That means if a cell contains "0" then the traveler is allowed to occupy that cell as this car can drive on roads. The traveler starts at the island located at latitude = 0 and longitude = 0 (i.e., (0,0)) in the upper left comer, and the goal is to drive to the island located at (MaxLattitude-1, MaxLongitudes-1) in the lower right corner. A legal move from an island is to move left, right, up, or down to an immediately adjacent cell…
1. Using the above class map, write function void map::mapToGraph(graph &g){...} to create a graph g that represents the legal moves in the map m. Each vertex should represent a cell, and each edge should represent a legal move between adjacent cells. 2. Write a recursive function findPathRecursive(graph &g, stack &moves) that looks for a path from the start island to the destination island. If a path from the start to the destination exists, your function should call the map::printPath() function that should print a sequence of correct moves (Go left, Go right, Go down, Go up, etc.). If no path from the start to the destination exists, the program should print, "No path exists". If a solution exists the solver should also simulate the solution to each map by calling the map::print() function. The map::print() function prints out a map visualization, with the goal and current position of the car in the map at each move, marked to show the progress. Hint: consider recursive-DFS. 3.…
Write a function that collects information from the user about a graph and builds an adjacency list representation of the graph; incorporate this function in the programs requested. Input: Information about a graph (see instructionsabove) and a node in the graphOutput: Nodes in a depth-first search of the graphbeginning with the given node
This task is solved in Python. 3. Write a function build_my_graph2 () that: a) creates the following Graph. b) runs Depth First Search (DFS) algorithm starting from node 'a' and prints all the visited nodes. What is printed in the output when you run the function? Note: you can use the implementation of Graph class and the DFS algorithm (provided in Lecture notes). 5.0 g h e
This task is solved in Python. 3. Write a function build_my_graph2 () that: a) creates the following Graph. b) runs Depth First Search (DFS) algorithm starting from node 'a' and prints all the visited nodes. What is printed in the output when you run the function? Note: you can use the implementation of Graph class and the DFS algorithm (provided in Lecture notes). class Graph: graph = dict() searched = [] def add_edge(self, node, neighbour): if node not in self.graph: self.graphinode] = [neighbour] else: self.graph[node].append(neighbour) def print_graph(self): print[self.graph) def depth first search(self, node): if node not in self.searched: print[[, node, end="1) self.searched.append(node)
This task is solved in Python. 3. Write a function build_my_graph2 () that: a) creates the following Graph. b) runs Depth First Search (DFS) algorithm starting from node 'a' and prints all the visited nodes. What is printed in the output when you run the function? Note: you can use the implementation of Graph class and the DFS algorithm (provided in Lecture notes). g h
the number of edges in a complete 2 of 2 undirected graph of 80 vertices is.? Select one: a. exactly equals 3160 b. None c. less than or equals 3160 d. less than or equals 6320 e. exactly equals 6320 Assume that you have a doubly link list. Pointer x is pointing to the last node in the link list and pointer y is pointing to before the last node. which of the following will remove the node pointed by x from the list? Select one: O a. delete x; b. y->prev->next = y->next; X->prev= y->prev; delete x; O C. X->prev->next = x->next; y->prev= x->prev; delete x; O d. x->next = y; y->prev = x->prev; delete x;
Write a function, called getadjacents, that receives a T item and an empty queue. The function will fill the queue with all items stored in vertices that are adjacent to the vertex containing the item sent as a parameter. The function belongs to a graph class with an adjacency list implementation. C++
09.Given a linked list of N nodes such that it may contain a loop. A loop here means that the last node of the link list is connected to the node at position X(1-based index). If the link list does not have any loop, X=0. Remove the loop from the linked list, if it is present, i.e. unlink the last node which is forming the loop. Example 1: Input: N = 3 value[] = {1,3,4} X = 2 Output: 1 Explanation: The link list looks like 1 -> 3 -> 4 ^ | |____|
Can you help me with a C++ programming task I am trying to complete for myself please: Write a program (in main.cpp) that: Prompts the user for a filename containing node data. Outputs the minimal spanning tree for a given graph. You will need to implement the createSpanningGraph method in minimalSpanTreeType.h to create the graph and the weight matrix. There are a few tabs: main.cpp, graphType.h, linkedList.h, linkedQueue.h, queueADT.h, minimalSpanTreeType.h, and then two data files labeled: CH20_Ex21Data.txt, CH20Ex4Data.txt
What the code is about: Implement a recursive algorithm to add all the elements of a non-dummy headed singly linked linear list. Only head of the list will be given as parameter where you may assume every node can contain only integer as its element.Note: you’ll need a Singly Node class for this code. **PLEASE EXPLAIN HOW THE NODE CLASS AND THE CONSTRUCTOR OF THE NODE CLASS IS WORKING IN THIS CODE** #singlty node class for single linked listclass node: def __init__(self, value = None, next=None): self.value = value self.next = nextdef AddAll(head):#takes head of single linked list head if head==None: return 0#if reached end of the linked list return AddAll(head.next) + head.value #each node's next pointer is passed in recursive call #and value of each node is added while returning from recursive call