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

5 votes

3 answers

61

Shortest path - bellman ford and floyd warshall
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 ... Floyd-Warshall algorithm correctly computes shortest path lengths between every pair of vertices. Which of them 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...

Tuhin Dutta

3.2k views

Tuhin Dutta asked Dec 10, 2017

12 votes

1 answer

62

TIFR CSE 2018 | Part B | Question: 9
Let $G=(V,E)$ be a DIRECTED graph, where each edge $\large e$ has a positive weight $\large\omega(e),$ and all vertices can be reached from vertex $\large s.$ For each vertex $\large v,$ let $\large \phi(v)$ be the length of the ... is NOT a shortest path in $G,$ then $\omega'(P)<2\times \omega(P).$ All of the above options are necessarily TRUE.

Let $G=(V,E)$ be a DIRECTED graph, where each edge $\large e$ has a positive weight $\large\omega(e),$ and all vertices can be reached from vertex $\large s.$ For each ve...

Arjun

2.4k views

Arjun asked Dec 10, 2017

0 votes

1 answer

63

Virtual gate

dushyantsingh

327 views

dushyantsingh asked Dec 2, 2017

–1 votes

1 answer

64

Dijkstra algorithm

Parshu gate

1.4k views

Parshu gate asked Nov 28, 2017

0 votes

0 answers

65

Open Shortest Path First

Parshu gate

756 views

Parshu gate asked Nov 28, 2017

2 votes

1 answer

66

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.

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, an...

shaurya vardhan

920 views

shaurya vardhan asked Nov 6, 2017

2 votes

0 answers

67

Bellman Ford Algorithm (Edge sequence and convergence of algo.)
Hi Guys, As everyone knows Bellman Ford Algorithm works on DP approach. The algorithm calculate shortest paths in bottom-up manner. It first calculates the shortest distances which have at-most one edge in the path. Then, ... is your opinion ? Refer --> http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/

Hi Guys,As everyone knows Bellman Ford Algorithm works on DP approach. The algorithm calculate shortest paths in bottom-up manner. It first calculates the shortest distan...

Chhotu

867 views

Chhotu asked Nov 3, 2017

3 votes

0 answers

68

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

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

Shivam Chauhan

914 views

Shivam Chauhan asked Nov 2, 2017

7 votes

0 answers

69

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.

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...

junaid ahmad

2.0k views

junaid ahmad asked Oct 12, 2017

1 votes

3 answers

70

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.

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 inc...

Warlock lord

1.5k views

Warlock lord asked Sep 14, 2017

1 votes

0 answers

71

How many simple path from u to v going through w?
A complete graph on n vertices is an undirected graph in which every pair of distinct vertices is connected by an edge. A simple path in a graph is one in which no vertex is repeated. Let G be a complete graph on 10 vertices. Let u, ... vertices in G. How many simple paths are there from u to v going through w? Please explain in detail. Thank you.

A complete graph on n vertices is an undirected graph in which every pair of distinct vertices is connected by an edge. A simple path in a graph is one in which no vertex...

Hemant Parihar

916 views

Hemant Parihar asked Sep 9, 2017

0 votes

1 answer

72

Please solve this Q with example
Question: 17 Consider two vertices a and b that are simultaneously on the FIFO queue at same point during the execution of breadth first search from s in an undirected graph. Which of the following is true? 1. The number of edges on the shortest path between ... less than the number of edges on the shortest path between s and b. 3. There is a path between a and b.

Question: 17 Consider two vertices a and b that are simultaneously on the FIFO queue at same point during the execution of breadth first search from s in an undirected g...

kallu singh

639 views

kallu singh asked Aug 20, 2017

1 votes

3 answers

73

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 ?

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 ...

Abhisek Saha

1.1k views

Abhisek Saha asked Jun 26, 2017

1 votes

2 answers

74

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.

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 i...

Shyam Singh 1

1.4k views

Shyam Singh 1 asked May 8, 2017

2 votes

4 answers

75

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

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

Bongbirdie

1.9k views

Bongbirdie asked Apr 6, 2017

2 votes

1 answer

76

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!?

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 negati...

Bongbirdie

860 views

Bongbirdie asked Apr 6, 2017

1 votes

1 answer

77

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

Using DIjkstra algorithm solve shortest path algorithm from A to D

LavTheRawkstar

984 views

LavTheRawkstar asked Apr 6, 2017

0 votes

0 answers

78

Calculate the shortest path using TSP Greedy Appraoch
Calculate the shortest path using TSP Greedy Appraoch

Calculate the shortest path using TSP Greedy Appraoch

LavTheRawkstar

423 views

LavTheRawkstar asked Mar 26, 2017

5 votes

1 answer

79

Testbook live Testseries
Which of the following statements are false ? $1.$ A depth-first search of a directed graph always produces the same number of tree edges (i.e., independent of the order in which the vertices are provided and independent of the order of ... between any two vertices will not change. $4.$ Dijkstra's algorithm may not terminate if the graph contains negative weight edges.

Which of the following statements are false ?$1.$ A depth-first search of a directed graph always produces the same number of tree edges (i.e., independent of the order i...

Akriti sood

2.3k views

Akriti sood asked Jan 23, 2017

1 votes

1 answer

80

Test by Bikram | Mock GATE | Test 1 | Question: 42
Find the missing statement in the if loop of $Floyd$ algorithm. Procedure Floyd: (var A: array[1...n,1...n] of real; C: array [1...n,1...n] of real); Var i, j, k: integer; begin M for i:=l to n do for j:=l to n do A[i,j]: =C[i,j] for i:=l to n do A[i,j ]:=0 ; ... $A[i,j]: = A[i, j] + A[k,j]$ $A[i,j]: = A[j,k]+ A[j,i]$ $A[i,j]: =A[i,k] + A[i,j]$

Find the missing statement in the if loop of $Floyd$ algorithm.Procedure Floyd: (var A: array[1...n,1...n] of real; C: array [1...n,1...n] of real); Var i, j, k: integer;...

Bikram

555 views

Bikram asked Jan 16, 2017

0 votes

3 answers

81

Ace Test Series

Vignesh Kamath

1.3k views

Vignesh Kamath asked Jan 14, 2017

0 votes

2 answers

82

CMI2016-A-4
Consider a weighted undirected graph $G$ with positive edge weights. Let $(u, v)$ be an edge in the graph. It is known that the shortest path from a vertex $s$ to $u$ has weight $53$ and the shortest path from $s$ to $v$ has weight $65.$ Which of the statements is always true? ... $(u, v) = 12$ Weight of $(u, v) \geq 12$ Nothing can be said about the weight of $(u, v)$

Consider a weighted undirected graph $G$ with positive edge weights. Let $(u, v)$ be an edge in the graph. It is known that the shortest path from a vertex $s$ to $u$ has...

go_editor

871 views

go_editor asked Dec 30, 2016

1 votes

2 answers

83

CMI2016-A-1
In a connected undirected graph, the distance between two vertices is the number of edges in the shortest path between them. Suppose we denote bt $P$ the following property: there exists a vertex that is a neighbour of all other vertices. Consider the following statements: If ... say about these statements? Only i is true Only ii is true Both i and ii are true Neither i nor ii is true

In a connected undirected graph, the distance between two vertices is the number of edges in the shortest path between them. Suppose we denote bt $P$ the following proper...

go_editor

1.1k views

go_editor asked Dec 30, 2016

1 votes

1 answer

84

MadeEasy Test Series: Algorithms - Graph Algorithms

rahul sharma 5

1.0k views

rahul sharma 5 asked Dec 13, 2016

3 votes

2 answers

85

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

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 sho...

dd

2.7k views

dd asked Dec 6, 2016

0 votes

1 answer

86

cormen
what will be the effect if we take equality in relaxaction condition of bellman ford algo??

what will be the effect if we take equality in relaxaction condition of bellman ford algo??

2018

321 views

2018 asked Nov 29, 2016

1 votes

3 answers

87

Find shortest path

Rakesh K

3.2k views

Rakesh K asked Nov 27, 2016

0 votes

8 answers

88

MadeEasy Test Series: Algorithms - Shortest Paths
Consider the following statements For every weighted graph and any two vertices $s$ and $t$, Bellman-Ford algorithm starting at $s$ will always return the shortest path to $t$. At the termination of the Bellman-ford algorithm, ... shortest path is found for a vertex for which shortest path is well-defined. Which of the above statements are true?

Consider the following statementsFor every weighted graph and any two vertices $s$ and $t$, Bellman-Ford algorithm starting at $s$ will always return the shortest path to...

vaishali jhalani

4.4k views

vaishali jhalani asked Nov 6, 2016

6 votes

1 answer

89

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)?

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)?

vaishali jhalani

3.0k views

vaishali jhalani asked Nov 5, 2016

2 votes

1 answer

90

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.

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. (As...

vaishali jhalani

743 views

vaishali jhalani asked Nov 5, 2016

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