Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions tagged shortest-path
4
votes
1
answer
31
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
Ruturaj Mohanty
asked
in
Algorithms
Dec 27, 2018
by
Ruturaj Mohanty
1.1k
views
go-mockgate-1
greedy-algorithm
dijkstras-algorithm
shortest-path
algorithms
graph-algorithms
0
votes
0
answers
32
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.
eyeamgj
asked
in
Algorithms
Nov 21, 2018
by
eyeamgj
178
views
shortest-path
0
votes
0
answers
33
Shortest Path
Vaishnavi01
asked
in
Algorithms
Nov 19, 2018
by
Vaishnavi01
163
views
algorithms
graph-algorithms
shortest-path
0
votes
1
answer
34
shortest path
Can shortest path contains positive weight cycle???Please explain with examples.
saumya mishra
asked
in
Algorithms
Nov 6, 2018
by
saumya mishra
166
views
shortest-path
graph-algorithms
1
vote
1
answer
35
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
2.1k
views
algorithms
bellman-ford
shortest-path
1
vote
1
answer
36
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
1.1k
views
shortest-path
algorithms
graph-algorithms
bellman-ford
1
vote
0
answers
37
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
447
views
graph-algorithms
shortest-path
1
vote
1
answer
38
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.6k
views
dijkstras-algorithm
shortest-path
space-complexity
algorithms
graph-algorithms
greedy-algorithm
1
vote
1
answer
39
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
by
kilopavan
1.1k
views
bellman-ford
shortest-path
0
votes
2
answers
40
#Algorithm Bellman Ford uses which algorithm design technique
Is it Dynamic programming?
iarnav
asked
in
Algorithms
May 17, 2018
by
iarnav
1.7k
views
algorithms
bellman-ford
shortest-path
graph-algorithms
2
votes
1
answer
41
# 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??
G Shaheena
asked
in
Algorithms
Apr 25, 2018
by
G Shaheena
362
views
algorithms
shortest-path
dijkstras-algorithm
0
votes
0
answers
42
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
196
views
shortest-path
algorithms
graph-algorithms
1
vote
1
answer
43
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 ... no -ve edge weight cycle reachable from source node. Am I correct with this? or am I missing something here?
GateAspirant999
asked
in
Algorithms
Feb 1, 2018
by
GateAspirant999
2.9k
views
dijkstras-algorithm
shortest-path
1
vote
3
answers
44
Dijkstra Algorithm
I think answer should be Option(B). Path:<s,y><y,x><x,t> = 7-3-2=2
ankit_thawal
asked
in
Algorithms
Jan 25, 2018
by
ankit_thawal
340
views
dijkstras-algorithm
shortest-path
algorithms
made-easy-test-series
1
vote
0
answers
45
algorithm
nikkey123
asked
in
Algorithms
Dec 31, 2017
by
nikkey123
209
views
algorithms
shortest-path
1
vote
1
answer
46
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?
garg div
asked
in
Algorithms
Dec 31, 2017
by
garg div
195
views
graph-algorithms
shortest-path
made-easy-test-series
2
votes
1
answer
47
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
814
views
algorithms
shortest-path
graph-algorithms
5
votes
3
answers
48
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
by
Tuhin Dutta
2.6k
views
algorithms
shortest-path
12
votes
1
answer
49
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 shortest ... $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.9k
views
tifr2018
graph-algorithms
shortest-path
0
votes
1
answer
50
Virtual gate
dushyantsingh
asked
in
Algorithms
Dec 2, 2017
by
dushyantsingh
155
views
virtual-gate-test-series
graph-theory
shortest-path
–1
vote
1
answer
51
Dijkstra algorithm
Parshu gate
asked
in
Computer Networks
Nov 29, 2017
by
Parshu gate
1.1k
views
dijkstras-algorithm
shortest-path
computer-networks
0
votes
0
answers
52
Open Shortest Path First
Parshu gate
asked
in
Computer Networks
Nov 28, 2017
by
Parshu gate
458
views
shortest-path
link-state-routing
computer-networks
2
votes
1
answer
53
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
702
views
algorithms
bellman-ford
shortest-path
2
votes
0
answers
54
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
705
views
algorithms
shortest-path
bellman-ford
graph-algorithms
3
votes
0
answers
55
Shortest Path
First Statement is true. But I don't know about second?
Shivam Chauhan
asked
in
Algorithms
Nov 2, 2017
by
Shivam Chauhan
550
views
shortest-path
algorithms
7
votes
0
answers
56
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
dijkstras-algorithm
shortest-path
1
vote
3
answers
57
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.
Warlock lord
asked
in
Algorithms
Sep 14, 2017
by
Warlock lord
1.0k
views
dijkstras-algorithm
algorithms
shortest-path
1
vote
0
answers
58
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.
Hemant Parihar
asked
in
Graph Theory
Sep 9, 2017
by
Hemant Parihar
799
views
graph-theory
shortest-path
0
votes
1
answer
59
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.
kallu singh
asked
in
Algorithms
Aug 20, 2017
by
kallu singh
488
views
graph-algorithms
shortest-path
1
vote
3
answers
60
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 ?
Abhisek Saha
asked
in
Algorithms
Jun 26, 2017
by
Abhisek Saha
848
views
algorithms
graph-algorithms
shortest-path
Page:
« prev
1
2
3
4
next »
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
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
POWER GRID CORPORATION OF INDIA LIMITED
INSTITUTE OF BANKING PERSONNEL SELECTION
GATE Overflow books for TIFR, ISRO, UGCNET and NIELIT
RECRUITMENT IN OIL AND GAS CORPORATION LIMITED
Aptitude Overflow Book
Subjects
All categories
General Aptitude
(2.4k)
Engineering Mathematics
(9.1k)
Digital Logic
(3.2k)
Programming and DS
(5.8k)
Algorithms
(4.5k)
Theory of Computation
(6.6k)
Compiler Design
(2.3k)
Operating System
(4.9k)
Databases
(4.5k)
CO and Architecture
(3.7k)
Computer Networks
(4.5k)
Non GATE
(1.3k)
Others
(2.4k)
Admissions
(647)
Exam Queries
(841)
Tier 1 Placement Questions
(17)
Job Queries
(74)
Projects
(9)
Unknown Category
(855)
Recent questions tagged shortest-path
Recent Blog Comments
@abir_banerjee Thanks Abir. I'm third year...
@nolan_keats Currently I am in third year...
@abir_banerjee thank you Abir.Supposing you...
@nolan_keats just a suggestion as I also...
@abir_banerjee Hope I can do this in span of one...