Recent questions tagged shortest-path

+2 votes

2 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$

asked Sep 13 in Graph Theory by gatecse Boss (16.8k points) | 29 views

+1 vote

1 answer

2

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

asked Oct 20, 2018 in Algorithms by Na462 Loyal (6.9k points) | 171 views

+1 vote

1 answer

3

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

asked Aug 3, 2018 in Algorithms by Sandy Sharma Active (1.2k points) | 233 views

+1 vote

0 answers

4

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.

asked Jul 31, 2018 in Algorithms by Rishav Kumar Singh Loyal (5.6k points) | 90 views

+1 vote

1 answer

5

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

asked Jul 5, 2018 in Algorithms by Hardik Maheshwari (93 points) | 592 views

0 votes

1 answer

6

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

asked Jun 1, 2018 in Algorithms by kilopavan (49 points) | 301 views

0 votes

2 answers

7

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

asked May 17, 2018 in Algorithms by iarnav Loyal (8.3k points) | 254 views

0 votes

0 answers

8

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?

asked Mar 24, 2018 in Programming by GateAspirant999 Active (2.5k points) | 70 views

+1 vote

0 answers

9

algorithm

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

0 votes

1 answer

10

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 Junior (697 points) | 209 views

+5 votes

3 answers

11

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?

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

+6 votes

1 answer

12

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.

asked Dec 10, 2017 in Algorithms by Arjun Veteran (425k points) | 332 views

+3 votes

2 answers

13

Dijkstra Algorithm

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

–1 vote

1 answer

14

Dijkstra algorithm

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

0 votes

0 answers

15

Open Shortest Path First

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

+2 votes

1 answer

16

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.1k points) | 237 views

+1 vote

0 answers

17

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/

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

+3 votes

0 answers

18

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) | 181 views

+7 votes

0 answers

19

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.5k points) | 633 views

0 votes

3 answers

20

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.3k points) | 246 views

+1 vote

0 answers

21

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.

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

+1 vote

3 answers

22

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 (151 points) | 280 views

+1 vote

2 answers

23

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.4k points) | 377 views

+2 votes

4 answers

24

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 (697 points) | 536 views

+2 votes

1 answer

25

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 (697 points) | 255 views

+1 vote

1 answer

26

#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 (3.7k points) | 228 views

0 votes

1 answer

27

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

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

0 votes

4 answers

28

Ace Test Series

asked Jan 14, 2017 in Algorithms by Vignesh Kamath (265 points) | 226 views

0 votes

1 answer

29

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

asked Dec 30, 2016 in Graph Theory by jothee Veteran (105k points) | 90 views

+1 vote

1 answer

30

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

asked Dec 30, 2016 in Graph Theory by jothee Veteran (105k points) | 99 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