Recent questions tagged shortest-path

Recent questions tagged shortest-path

6 votes

3 answers

1

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$

gatecse asked in Graph Theory Sep 13, 2019

485 views

4 votes

1 answer

2

GO2019-FLT1-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 with negative weight edges. ( ... P, Q, S, T and U are correct Only Q, R, T are correct Only Q, R, S, T and U are correct

Ruturaj Mohanty asked in Algorithms Dec 27, 2018

by Ruturaj Mohanty

844 views

1 vote

1 answer

3

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

Na462 asked in Algorithms Oct 20, 2018

by Na462

1.9k views

1 vote

1 answer

4

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

Sandy Sharma asked in Algorithms Aug 3, 2018

by Sandy Sharma

987 views

1 vote

0 answers

5

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.

Rishav Kumar Singh asked in Algorithms Jul 31, 2018

by Rishav Kumar Singh

375 views

1 vote

1 answer

6

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

Hardik Maheshwari asked in Algorithms Jul 5, 2018

by Hardik Maheshwari

2.5k views

1 vote

1 answer

7

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

kilopavan asked in Algorithms Jun 1, 2018

984 views

0 votes

2 answers

8

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

iarnav asked in Algorithms May 17, 2018

by iarnav

1.5k views

0 votes

0 answers

9

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?

GateAspirant999 asked in Programming Mar 24, 2018

by GateAspirant999

179 views

1 vote

0 answers

10

nikkey123 asked in Algorithms Dec 31, 2017

192 views

2 votes

1 answer

11

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.

VIKAS TIWARI asked in Algorithms Dec 13, 2017

by VIKAS TIWARI

705 views

5 votes

3 answers

12

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?

Tuhin Dutta asked in Algorithms Dec 10, 2017

2.4k views

12 votes

1 answer

13

TIFR2018-B-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 shortest path from $\large s$ ... If $P$ is NOT a shortest path in $G,$ then $\omega'(P)<2\times \omega(P).$ All of the above options are necessarily TRUE.

Arjun asked in Algorithms Dec 10, 2017

by Arjun

1.7k views

4 votes

2 answers

14

Dijkstra Algorithm

Parshu gate asked in Algorithms Dec 5, 2017

2.1k views

–1 vote

1 answer

15

Dijkstra algorithm

Parshu gate asked in Computer Networks Nov 29, 2017

1.0k views

0 votes

0 answers

16

Open Shortest Path First

Parshu gate asked in Computer Networks Nov 28, 2017

415 views

2 votes

1 answer

17

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.

shaurya vardhan asked in Algorithms Nov 6, 2017

by shaurya vardhan

655 views

2 votes

0 answers

18

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/

Chhotu asked in Algorithms Nov 3, 2017

by Chhotu

657 views

3 votes

0 answers

19

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

Shivam Chauhan asked in Algorithms Nov 2, 2017

by Shivam Chauhan

451 views

7 votes

0 answers

20

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.

junaid ahmad asked in Algorithms Oct 12, 2017

by junaid ahmad

1.6k views

Page:

Follow @gateoverflow

Recent questions tagged shortest-path

Search GATE Overflow for GATE CSE