The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged shortestpath
+2
votes
2
answers
1
CMI2018A4
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
cmi2018
graphtheory
undirectedgraph
simplegraph
shortestpath
+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
algorithms
bellmanford
shortestpath
+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? BELLMANFORD(G,w,s) Code 1. INITIALIZESINGLESOURCE(G,s) 2. for i = 1 to G.V1 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
shortestpath
algorithms
graphalgorithms
bellmanford
+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
graphalgorithms
shortestpath
+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/algorithmspacetimecomplexity) But how ????
asked
Jul 5, 2018
in
Algorithms
by
Hardik Maheshwari
(
93
points)

592
views
dijkstrasalgorithm
shortestpath
spacecomplexity
algorithms
graphalgorithms
greedyalgorithm
0
votes
1
answer
6
Regarding the complexity of BellmanFord ?
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
bellmanford
shortestpath
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
algorithms
bellmanford
shortestpath
graphalgorithms
selfdoubt
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 allpairs shortestpaths problem on an input adjacency matrix, we need to compute not only the shortestpath weights but also a predecessor ... isnt both things (shortestpaths 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
shortestpath
algorithms
graphalgorithms
+1
vote
0
answers
9
algorithm
asked
Dec 31, 2017
in
Algorithms
by
nikkey123
Active
(
1.2k
points)

67
views
algorithms
shortestpath
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
algorithms
shortestpath
graphalgorithms
negativecycles
+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 BellmanFord algorithm correctly computes shortest path ... FloydWarshall 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
algorithms
shortestpath
bellmanford
negativecycles
+6
votes
1
answer
12
TIFR2018B9
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
tifr2018
graphalgorithms
shortestpath
+3
votes
2
answers
13
Dijkstra Algorithm
asked
Dec 5, 2017
in
Algorithms
by
Parshu gate
Active
(
3.1k
points)

462
views
dijkstrasalgorithm
shortestpath
algorithms
–1
vote
1
answer
14
Dijkstra algorithm
asked
Nov 29, 2017
in
Computer Networks
by
Parshu gate
Active
(
3.1k
points)

305
views
dijkstrasalgorithm
shortestpath
computernetworks
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
shortestpath
linkstaterouting
computernetworks
+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 V1. (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
algorithms
bellmanford
shortestpath
graphalgorithms
negativecycles
+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 bottomup manner. It first calculates the shortest distances which have atmost one edge in the path. Then, ... is your opinion ? Refer > http://www.geeksforgeeks.org/dynamicprogrammingset23bellmanfordalgorithm/
asked
Nov 3, 2017
in
Algorithms
by
Chhotu
Boss
(
13.3k
points)

304
views
algorithms
shortestpath
bellmanford
graphalgorithms
+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
shortestpath
algorithms
+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
dijkstrasalgorithm
shortestpath
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
dijkstrasalgorithm
algorithms
shortestpath
+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
graphtheory
shortestpath
+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
algorithms
graphalgorithms
shortestpath
+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 welldefined.
asked
May 8, 2017
in
Algorithms
by
Shyam Singh 1
Active
(
1.4k
points)

377
views
shortestpath
+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
algorithms
shortestpath
bellmanford
negativecycles
+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
shortestpath
bellmanford
algorithms
+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
algorithms
shortestpath
dijkstrasalgorithm
computernetworks
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
algorithms
shortestpath
0
votes
4
answers
28
Ace Test Series
asked
Jan 14, 2017
in
Algorithms
by
Vignesh Kamath
(
265
points)

226
views
algorithms
shortestpath
acetestseries
0
votes
1
answer
29
CMI2016A4
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
cmi2016
graphtheory
undirectedgraph
shortestpath
+1
vote
1
answer
30
CMI2016A1
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
cmi2016
graphtheory
undirectedgraph
shortestpath
Page:
1
2
next »
Quick search syntax
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 Posts
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Follow @csegate
Recent questions tagged shortestpath
Recent Blog Comments
Lakshman Patel RJIT Do you have such notes...
Great work sir
Yes Sir, It will be very helpful if we get...
@arjun sir is there a pdf...
Really helpful sir Thanks a ton👍👍
50,645
questions
56,559
answers
195,717
comments
101,599
users