Recent questions tagged shortest-path / GATE Overflow for GATE CSE

2 votes

1 answer

31

GATE Overflow Test Series | Algorithms | Test 2 | Question: 4
Let $G(V, E)$ be an undirected graph with some edge weights being negative but without any negative weight cycle. Which of the following is/are TRUE when $G$ is given as input with a given source $s$? (Mark all ... all vertices from $s$ Bellman-Ford algorithm will always fail to correctly output the shortest path to all vertices from $s$

Let $G(V, E)$ be an undirected graph with some edge weights being negative but without any negative weight cycle. Which of the following is/are TRUE when $G$ is given as ...

gatecse

249 views

gatecse asked Sep 7, 2020

5 votes

1 answer

32

GATE Overflow Test Series | Algorithms | Test 2 | Question: 5
Which of the following algorithm can be used to efficiently calculate single source shortest paths in a Directed Acyclic Graph where all edge weights are equal? Dijkstra's algorithm Bellman-Ford algorithm Topological Sort Prim's algorithm

Which of the following algorithm can be used to efficiently calculate single source shortest paths in a Directed Acyclic Graph where all edge weights are equal?Dijkstra's...

gatecse

284 views

gatecse asked Sep 7, 2020

4 votes

1 answer

33

GATE Overflow Test Series | Algorithms | Test 2 | Question: 6
Given a directed graph where weight of every edge is same, we can efficiently find the shortest path from a given source to destination using _____ Breadth First Traversal Dijkstra's Shortest Path Algorithm Bellman-Ford Algorithm Depth First Search

Given a directed graph where weight of every edge is same, we can efficiently find the shortest path from a given source to destination using _____Breadth First Traversal...

gatecse

188 views

gatecse asked Sep 7, 2020

4 votes

1 answer

34

GATE Overflow Test Series | Algorithms | Test 2 | Question: 18
Which of the following statements is/are TRUE with respect to the time complexities of the graph algorithms to find Single Source Shortest Path (SSSP)? (Mark all the appropriate choices) Bellman-Ford algorithm to find SSSP runs in $O(VE)$ Dijkstra ... $O(|V|+|E|)$

Which of the following statements is/are TRUE with respect to the time complexities of the graph algorithms to find Single Source Shortest Path (SSSP)? (Mark all the appr...

gatecse

266 views

gatecse asked Sep 7, 2020

6 votes

1 answer

35

GATE Overflow Test Series | Algorithms | Test 2 | Question: 22
Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices $c$ and $e$. Which one will be reported by Dijstra's shortest path algorithm run with $a$ as the source? Assume that, in any iteration, the shortest path to ... path to $v$ is discovered. $c-d-f-e$ $c-f-e$ $c-i-g-f-e$ $c-d-e$

Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices $c$ and $e$. Which one will be reported by Dijstra's shortest pa...

gatecse

280 views

gatecse asked Sep 7, 2020

5 votes

1 answer

36

GATE Overflow Test Series | Algorithms | Test 2 | Question: 24
Which of the following is/are correct with respect to Dijkstra's algorithm to find Single Source Shortest Path in a weighted directed graph $G$? (Mark all the appropriate choices) Dijkstra's algorithm runs in $O(|E| \lg |V|)$ ... has a worst case time complexity of $O(|V|\lg |V| + |E|)$ when implemented with a Fibonacci heap

Which of the following is/are correct with respect to Dijkstra's algorithm to find Single Source Shortest Path in a weighted directed graph $G$? (Mark all the appropriate...

gatecse

465 views

gatecse asked Sep 7, 2020

3 votes

1 answer

37

GATE Overflow Test Series | Algorithms | Test 2 | Question: 25
Suppose we run Dijkstra's single source shortest-path algorithm on the following edge weighted directed graph with vertex $a$ as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized? (Assume that whenever ... $a,b,g,c,h,e,d,f$ $a,b,c,h,g,f,e,d$

Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge weighted directed graph with vertex $a$ as the source. In what order do the nodes ...

gatecse

142 views

gatecse asked Sep 7, 2020

5 votes

1 answer

38

GATE Overflow Test Series | Algorithms | Test 2 | Question: 26
Which of the following statement(s) is/are correct regarding Bellman-Ford single source shortest path algorithm? (Mark all the appropriate choices) Always finds the correct shortest path even when edge weights are ... negative weighted cycle is reachable from the source. Performs better than Dijkstra's algorithm for dense graphs

Which of the following statement(s) is/are correct regarding Bellman-Ford single source shortest path algorithm?(Mark all the appropriate choices)Always finds the correct...

gatecse

265 views

gatecse asked Sep 7, 2020

6 votes

3 answers

39

GATE Overflow Test Series | Algorithms | Test 2 | Question: 28
Let $G$ be a directed graph whose vertex set is the set of numbers from $0$ to $100$. There is an edge from a vertex $i$ to a vertex $j$ if either $j = i + 2$ or $j = 7i$. The minimum number of edges in a path in $G$ from vertex $0$ to vertex $100$ is __________

Let $G$ be a directed graph whose vertex set is the set of numbers from $0$ to $100$. There is an edge from a vertex $i$ to a vertex $j$ if either $j = i + 2$ or $j = 7i$...

gatecse

217 views

gatecse asked Sep 7, 2020

5 votes

1 answer

40

GATE Overflow Test Series | Algorithms | Test 2 | Question: 29
Consider a weighted undirected graph with distinct positive edge weights and let $(u,v)$ be an edge in the graph. It is known that the shortest path from the source vertex $s$ to $u$ has weight $36$ and the shortest path from $s$ to $v$ has weight $44$. ... $(u, v) \leq 8$ weight $(u, v) > 8$ weight $(u, v) \geq 8$

Consider a weighted undirected graph with distinct positive edge weights and let $(u,v)$ be an edge in the graph. It is known that the shortest path from the source verte...

gatecse

252 views

gatecse asked Sep 7, 2020

6 votes

3 answers

41

CMI2018-A-4
Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$ For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ For an edge $(u,v)$ in $G,$ what can not be the value of $d(u)-d(v)?$ $2$ $-1$ $0$ $1$

Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$ For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ ...

gatecse

786 views

gatecse asked Sep 13, 2019

0 votes

1 answer

42

Made Easy Test Series:Algorithm- Minimum Weight Path
Consider the following statement: $A)$ If all edge weight of a graph are positive then any subset of edges that connect all vertices and has minimum total weight is a tree. $B)$ ... minimum weight graph?? and what about B)?? Is it just saying each minimum path between $2$ vertices makes total shortest path??

Consider the following statement:$A)$ If all edge weight of a graph are positive then any subset of edges that connect all vertices and has minimum total weight is a tree...

srestha

459 views

srestha asked May 10, 2019

0 votes

1 answer

43

Virtual Gate Test Series: Algorithms - Graphs

SameekshaGupta

489 views

SameekshaGupta asked Jan 13, 2019

4 votes

1 answer

44

GATE Overflow | Mock GATE | Test 1 | Question: 47
Which of the following statements is/are correct with respect to Djikstra Algorithm? (P) It always works perfectly for graphs with negative weight edges. (Q) It does not work perfectly for graphs with negative weight cycles. (R) It may or may not work for graphs ... , S, T and U are correct Only Q, R, T are correct Only Q, R, S, T and U are correct

Which of the following statements is/are correct with respect to Djikstra Algorithm?(P) It always works perfectly for graphs with negative weight edges.(Q) It does not wo...

Ruturaj Mohanty

1.6k views

Ruturaj Mohanty asked Dec 27, 2018

0 votes

0 answers

45

self doubt multistaGE GRAPH
https://gateoverflow.in/86958/find-shortest-path IN THIS QUESTION WHEN WE DO FINDING FROM END A SITUATION CAME WHERE WE HAVE TWO PATH FROM 8 OF LENGTH 3 EACH SO WHERE TO MOVE NOW AND I AM FINDING MINIMUM LENGTH 14 BUT ANSWER SAYS 15.

https://gateoverflow.in/86958/find-shortest-pathIN THIS QUESTION WHEN WE DO FINDING FROM END A SITUATION CAME WHERE WE HAVE TWO PATH FROM 8 OF LENGTH 3 EACH SO WHERE TO M...

eyeamgj

298 views

eyeamgj asked Nov 21, 2018

0 votes

0 answers

46

Shortest Path

Vaishnavi01

302 views

Vaishnavi01 asked Nov 19, 2018

0 votes

1 answer

47

shortest path
Can shortest path contains positive weight cycle???Please explain with examples.

Can shortest path contains positive weight cycle???Please explain with examples.

saumya mishra

278 views

saumya mishra asked Nov 6, 2018

1 votes

1 answer

48

Bellmann Ford Algorithm
Consider following with respect to directed graph where there can be positive,negative edge weights but no negative edge cycle. S1 : The Bellmann Ford algorithm will compute correctly the shortest path from source vertex S to every other Vertex. S2 : The Floyd Warshall ... pair of Verices. Which of Following statements are Correct ? A. Only S1 B. Only S2 C. Both D. None

Consider following with respect to directed graph where there can be positive,negative edge weights but no negative edge cycle.S1 : The Bellmann Ford algorithm will compu...

Na462

2.4k views

Na462 asked Oct 20, 2018

1 votes

1 answer

49

How Bellman ford is dynamic programming?
What is the reason behind it? How do we find an optimal substructure and overlapping sub problems in this ? In which line of code memoization is done? BELLMAN-FORD(G,w,s) Code 1. INITIALIZE-SINGLE-SOURCE(G,s) 2. for i = 1 to |G.V|-1 3. for each edge (u,v) ∈ G.E 4. RELAX(u,v,w) ... 0 RELAX(u,v,w) 1. if v.d > u.d + w(u,v) 2. v.d = u.d + w(u,v) 3. v.pi = u

What is the reason behind it? How do we find an optimal substructure and overlapping sub problems in this ? In which line of code memoization is done? BELLMAN-FORD(G,w,s)...

Sandy Sharma

1.4k views

Sandy Sharma asked Aug 3, 2018

1 votes

0 answers

50

shortest path algo
TRUE / FALSE Explain Please.. An undirected graph is said to be Hamiltonian if it has a cycle containing all the vertices. Any DFS tree on a Hamiltonian graph must have depth V − 1.

TRUE / FALSE Explain Please..An undirected graph is said to be Hamiltonian if it has a cycle containing all the vertices. Any DFS tree on a Hamiltonian graph must have de...

Rishav Kumar Singh

773 views

Rishav Kumar Singh asked Jul 30, 2018

2 votes

1 answer

51

Space Complexity of Dijkastra's algorithm
I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithm-space-time-complexity) But how ????

I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithm-space-time-complexity)But how ????

Hardik Maheshwari

3.0k views

Hardik Maheshwari asked Jul 5, 2018

1 votes

1 answer

52

Regarding the complexity of Bellman-Ford ?
In the adjacency list implementation of Bellman Ford algorithm every edge is visited at most one time and total of |E| are present in the adjacency list. So,how can the complexity be O(VE) why can't it be O(E) .Though it has two loops on whole it will run for |E| times. ??

In the adjacency list implementation of Bellman Ford algorithm every edge is visited at most one time and total of |E| are present in the adjacency list. So,how can the...

kilopavan

1.3k views

kilopavan asked Jun 1, 2018

0 votes

2 answers

53

#Algorithm Bellman Ford uses which algorithm design technique
Is it Dynamic programming?

Is it Dynamic programming?

iarnav

2.3k views

iarnav asked May 17, 2018

2 votes

1 answer

54

# Self doubt
To get in shape, you have decided to start running to work. You want a route that goes entirely uphill and then entirely downhill so that you can work up a sweat going uphill and then get a nice breeze at the end of your run as you ... Assuming that every road segment is either uphill or downhill, give an efficient algorithm to find out shortest route that meets above specification??

To get in shape, you have decided to start running to work. You want a route that goes entirely uphill and then entirely downhill so that you can work up a sweat going up...

G Shaheena

679 views

G Shaheena asked Apr 25, 2018

0 votes

0 answers

55

Equality of shortest path tree for given node as a root and
I have a small doubt. Chapter 25 All pairs shortest path of CLRS says following: To solve the all-pairs shortest-paths problem on an input adjacency matrix, we need to compute not only the shortest-path weights but also a predecessor ... isnt both things (shortest-paths tree with root $i$ and predecessor subgraph of $G$ for $i$) the same?

I have a small doubt.Chapter 25 All pairs shortest path of CLRS says following:To solve the all-pairs shortest-paths problem on an input adjacency matrix, we need to comp...

GateAspirant999

348 views

GateAspirant999 asked Mar 24, 2018

1 votes

1 answer

56

Negative edge weights in Dijkstra
All text books and online resources say Dijkstra's algorithm need all non negative edge weights However I feel a bit different, especially after coming across problem asking to build shortest path tree from node aa in following graph: My shortest path ... -ve edge weight cycle reachable from source node. Am I correct with this? or am I missing something here?

All text books and online resources say Dijkstra's algorithm need all non negative edge weightsHowever I feel a bit different, especially after coming across problem aski...

GateAspirant999

3.5k views

GateAspirant999 asked Feb 1, 2018

1 votes

3 answers

57

Dijkstra Algorithm
I think answer should be Option(B). Path:<s,y><y,x><x,t> = 7-3-2=2

I think answer should be Option(B).Path:<s,y><y,x><x,t = 7-3-2=2

ankit_thawal

1.6k views

ankit_thawal asked Jan 25, 2018

1 votes

0 answers

58

algorithm

nikkey123

309 views

nikkey123 asked Dec 31, 2017

1 votes

1 answer

59

madeeasy
Consider the following statements with respect to a directed graph G in which edges can have positive or negative edge length but that has no negative cycles: S1 : The Bellman-Ford algorithm correctly computes shortest path lengths from a given ... The Floyd-Warshall algorithm correctly computes shortest path lengths between every pair of vertices. Which of the following is correct?

Consider the following statements with respect to a directed graph G in which edges can have positive or negative edge length but that has no negative cycles:S1 : The Be...

garg div

370 views

garg div asked Dec 31, 2017

2 votes

1 answer

60

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.

Read the following statements belowFor all the below questions consider the graph as simple and has positive weight edges.(i) Let the cost of the shortest path between tw...

VIKAS TIWARI

999 views

VIKAS TIWARI asked Dec 13, 2017

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