Recent questions tagged shortest-path

0 votes

0 answers

1

Space Complexity of Dijkastra's algorithm

asked Jul 5 in Algorithms by Hardik Maheshwari (59 points) | 72 views

0 votes

1 answer

2

Regarding the complexity of Bellman-Ford ?

asked Jun 1 in Algorithms by kilopavan (11 points) | 52 views

0 votes

2 answers

3

#Algorithm Bellman Ford uses which algorithm design technique

asked May 17 in Algorithms by iarnav Loyal (7.4k points) | 75 views

0 votes

0 answers

4

Equality of shortest path tree for given node as a root and

asked Mar 24 in Programming by GateAspirant999 Active (2.6k points) | 44 views

+1 vote

0 answers

5

algorithm

asked Dec 31, 2017 in Algorithms by nikkey123 Active (1.5k points) | 49 views

0 votes

1 answer

6

shortest path
Read the following statements below For all the below questions consider the graph as simple and has positive weight edges. (i) Let the cost of the shortest path between two nodes is S.If the weight of every edge in the graph is doubled then weight of the ... We can use Kruskal's algorithm to find Minimum spanning tree of a directed graph . How many of the above statements are true.

asked Dec 13, 2017 in Algorithms by VIKAS TIWARI (343 points) | 156 views

+4 votes

2 answers

7

Shortest path - bellman ford and floyd warshall

asked Dec 10, 2017 in Algorithms by Tuhin Dutta Loyal (7.8k points) | 566 views

+2 votes

1 answer

8

Dijkstra Algorithm

asked Dec 5, 2017 in Algorithms by Parshu gate Active (4.9k points) | 217 views

–1 vote

1 answer

9

Dijkstra algorithm

asked Nov 29, 2017 in Computer Networks by Parshu gate Active (4.9k points) | 160 views

0 votes

0 answers

10

Open Shortest Path First

asked Nov 28, 2017 in Computer Networks by Parshu gate Active (4.9k points) | 81 views

+2 votes

2 answers

11

Testbook Test
(1). Both BFS and DFS require $\Omega (N)$ storage for their operation. (2). If we double the weight of every edge in the Graph shortest path between any two vertices will not change. Which of the following is/are True ? (and in every question of shortest path we have to think about negative weight ?)

asked Nov 7, 2017 in Algorithms by Mr_22B Active (1.1k points) | 255 views

+2 votes

1 answer

12

Bellman Ford
A pseudo code for Bellman Ford where each edge is relaxed k times where k>=1. Let the graph G be a simple connected and undirected graph . Let number of vertices be V, and number of edges be E . int i=1; for( i=1;i<=k;i++) { For each edge (u,v) ... . (ii) For proper running of the algorithm k can be equal to V-1. (iii) For proper running of the algorithm k must be equal to E.

asked Nov 6, 2017 in Algorithms by shaurya vardhan Active (2.2k points) | 123 views

+1 vote

0 answers

13

Bellman Ford Algorithm (Edge sequence and convergence of algo.)

asked Nov 3, 2017 in Algorithms by Chhotu Boss (10.6k points) | 188 views

+3 votes

0 answers

14

Shortest Path
First Statement is true. But I don't know about second?

asked Nov 2, 2017 in Algorithms by Shivam Chauhan Loyal (8.8k points) | 139 views

+5 votes

0 answers

15

Dijkstra's
I know that Dijkstra's Doesn't work for Negative weight cycle because it form a loop, Does it also true that it may or may not work for negative weight edge(without cycle) ? If it is not working for a negative weight edge(without cycle) give some example to prove it.

asked Oct 12, 2017 in Algorithms by junaid ahmad Loyal (8.9k points) | 275 views

0 votes

2 answers

16

dijkstra
If we run Dijkstra’s algorithm to find single source shortest path for the above edge weighted directed graph with ‘8’ as source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized.

asked Sep 14, 2017 in Algorithms by Warlock lord Active (3.4k points) | 147 views

+1 vote

0 answers

17

How many simple path from u to v going through w?

asked Sep 9, 2017 in Graph Theory by Hemant Parihar Boss (14.8k points) | 124 views

+1 vote

2 answers

18

Shortest Path Algorithms
For a given undirected weighted graph G with V number of vertices, if you want to find all pair shortest paths then which one of the following is true ? a) run dijkstra's shortest path algorithm only once. b) run dijkstra's shortest path algorithm V times. What if the given graph is directed ?

asked Jun 26, 2017 in Algorithms by Abhisek Saha (101 points) | 206 views

+1 vote

1 answer

19

Shortest path
I have 2 doubts below, each can be True or False? a) Dijkstra's Algo will terminate even if there is a -ve edge or -ve cycle. b) At the termination of Bellman Ford, even if graph has -ve cycle, a correct shortest path is found for a vertex for which shortest path is well-defined.

asked May 8, 2017 in Algorithms by Shyam Singh 1 Active (1.5k points) | 277 views

+2 votes

3 answers

20

Bellman Ford Shortest path
Is the below statement correct: Bellman Ford finds all negative weight cycles in the graph. This is true or false?

asked Apr 7, 2017 in Algorithms by Bongbirdie Junior (683 points) | 334 views

+2 votes

1 answer

21

Bellman Ford
If there is a negative edge cycle present in a graph, we all know that Bellman Ford has the capability to detect it. My doubt is that, even after the presence of a negative weighted cycle, will Bellman Ford Algorithm give the correct answer or it will simply say NO..shortest path cannot be computed!?

asked Apr 7, 2017 in Algorithms by Bongbirdie Junior (683 points) | 184 views

+1 vote

1 answer

22

#Totally Confused# please tell Using Dijkstra Algorithm solve shortest path algorithm from A to D.

asked Apr 6, 2017 in Computer Networks by LavTheRawkstar Active (5k points) | 166 views

0 votes

0 answers

23

Calculate the shortest path using TSP Greedy Appraoch

asked Mar 26, 2017 in Algorithms by LavTheRawkstar Active (5k points) | 96 views

0 votes

2 answers

24

Ace Test Series

asked Jan 14, 2017 in Algorithms by Vignesh Kamath (263 points) | 197 views

+3 votes

1 answer

25

shortest path
Let P be a shortest path from some vertex s to some other vertex t in a directed graph. If the weight of each edge in the graph is increased by one, P will still be a shortest path from s to t. T/F

asked Dec 6, 2016 in Algorithms by Debashish Deka Veteran (56.8k points) | 262 views

+1 vote

3 answers

26

Find shortest path

asked Nov 27, 2016 in Algorithms by Rakesh K Active (1.8k points) | 554 views

0 votes

2 answers

27

Bellman-ford

asked Nov 6, 2016 in Algorithms by vaishali jhalani Loyal (5.8k points) | 515 views

+4 votes

1 answer

28

Dijkstra's algorithm
What is the time complexity of Dijkstra’s algorithm if it is implemented using AVL Tree instead of Priority Queue over a graph G = (V, E)?

asked Nov 5, 2016 in Algorithms by vaishali jhalani Loyal (5.8k points) | 664 views

+2 votes

1 answer

29

maximum distance
Apply single source shortest path algorithm on the given graph using vertex ‘A’ as the source. What is the maximum possible distance between vertex A to vertex G. (Assume exclude infinity). Ans is 28.

asked Nov 5, 2016 in Algorithms by vaishali jhalani Loyal (5.8k points) | 145 views

0 votes

1 answer

30

Dijkstra's Agorithm
When the graph contain negetive weight edges but no negetive weight cycle, in this case can dijkstra leads to incorrect result?

asked Nov 4, 2016 in Algorithms by vaishali jhalani Loyal (5.8k points) | 230 views

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

Recent questions tagged shortest-path

Recent Posts

Recent Blog Comments