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

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions.
Recent questions tagged shortestpath
+1
vote
0
answers
1
algorithm
asked
Dec 31, 2017
in
Algorithms
by
nikkey123
Active
(
1.9k
points)

34
views
algorithms
shortestpath
0
votes
1
answer
2
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 ... 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
(
347
points)

112
views
algorithms
shortestpath
graphalgorithms
negativecycles
+4
votes
2
answers
3
Shortest path  bellman ford and floyd warshall
asked
Dec 10, 2017
in
Algorithms
by
Tuhin Dutta
Boss
(
7.9k
points)

414
views
algorithms
shortestpath
bellmanford
negativecycles
+2
votes
1
answer
4
Dijkstra Algorithm
asked
Dec 5, 2017
in
Algorithms
by
Parshu gate
Boss
(
6.5k
points)

147
views
dijkstrasalgorithm
shortestpath
algorithms
–1
vote
1
answer
5
Dijkstra algorithm
asked
Nov 29, 2017
in
Computer Networks
by
Parshu gate
Boss
(
6.5k
points)

98
views
dijkstrasalgorithm
shortestpath
computernetworks
0
votes
0
answers
6
Open Shortest Path First
asked
Nov 28, 2017
in
Computer Networks
by
Parshu gate
Boss
(
6.5k
points)

68
views
shortestpath
ospf
computernetworks
+2
votes
2
answers
7
Testbook Test
(1). Both BFS and DFS require $\Omega (N)$ storage for their operation. (2). If we double the weight of every edge in the Graph shortest path between any two vertices will not change. Which of the following is/are True ? (and in every question of shortest path we have to think about negative weight ?)
asked
Nov 7, 2017
in
Algorithms
by
Mr_22B
Active
(
1.6k
points)

222
views
shortestpath
algorithms
testbooktestseries
timecomplexity
+2
votes
1
answer
8
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 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
Loyal
(
4.1k
points)

93
views
algorithms
bellmanford
shortestpath
graphalgorithms
negativecycles
+1
vote
0
answers
9
Bellman Ford Algorithm (Edge sequence and convergence of algo.)
asked
Nov 3, 2017
in
Algorithms
by
Chhotu
Veteran
(
14.7k
points)

108
views
algorithms
shortestpath
bellmanford
graphalgorithms
+3
votes
0
answers
10
Shortest Path
First Statement is true. But I don't know about second?
asked
Nov 2, 2017
in
Algorithms
by
Shivam Chauhan
Boss
(
9.3k
points)

119
views
shortestpath
algorithms
+5
votes
0
answers
11
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
Veteran
(
12.6k
points)

179
views
dijkstrasalgorithm
shortestpath
0
votes
2
answers
12
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
Loyal
(
3.3k
points)

122
views
dijkstrasalgorithm
algorithms
shortestpath
+1
vote
0
answers
13
How many simple path from u to v going through w?
asked
Sep 9, 2017
in
Graph Theory
by
Hemant Parihar
Veteran
(
15.1k
points)

103
views
graphtheory
shortestpath
+1
vote
2
answers
14
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
(
137
points)

173
views
algorithms
graphalgorithms
shortestpath
+1
vote
1
answer
15
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.6k
points)

244
views
shortestpath
+2
votes
3
answers
16
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
(
821
points)

288
views
algorithms
shortestpath
bellmanford
negativecycles
+2
votes
1
answer
17
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
(
821
points)

160
views
shortestpath
bellmanford
algorithms
+1
vote
1
answer
18
#Totally Confused# please tell Using Dijkstra Algorithm solve shortest path algorithm from A to D.
asked
Apr 6, 2017
in
Computer Networks
by
LavTheRawkstar
Boss
(
6.8k
points)

152
views
algorithms
shortestpath
dijkstrasalgorithm
computernetworks
0
votes
0
answers
19
Calculate the shortest path using TSP Greedy Appraoch
asked
Mar 26, 2017
in
Algorithms
by
LavTheRawkstar
Boss
(
6.8k
points)

86
views
algorithms
shortestpath
travel
salesman
0
votes
2
answers
20
Ace Test Series
asked
Jan 14, 2017
in
Algorithms
by
Vignesh Kamath
(
323
points)

187
views
algorithms
shortestpath
acetestseries
+3
votes
1
answer
21
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
asked
Dec 6, 2016
in
Algorithms
by
Debashish Deka
Veteran
(
59.9k
points)

230
views
graphalgorithms
shortestpath
graphtheory
+1
vote
3
answers
22
Find shortest path
asked
Nov 27, 2016
in
Algorithms
by
Rakesh K
Active
(
2.2k
points)

481
views
graphalgorithms
shortestpath
algorithms
graphtheory
dynamicprogramming
multistagegraph
0
votes
2
answers
23
Bellmanford
asked
Nov 6, 2016
in
Algorithms
by
vaishali jhalani
Boss
(
7.1k
points)

458
views
algorithms
shortestpath
+4
votes
1
answer
24
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)?
asked
Nov 5, 2016
in
Algorithms
by
vaishali jhalani
Boss
(
7.1k
points)

554
views
algorithms
dijkstrasalgorithm
graphalgorithms
shortestpath
+2
votes
1
answer
25
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.
asked
Nov 5, 2016
in
Algorithms
by
vaishali jhalani
Boss
(
7.1k
points)

137
views
algorithms
shortestpath
0
votes
1
answer
26
Dijkstra's Agorithm
When the graph contain negetive weight edges but no negetive weight cycle, in this case can dijkstra leads to incorrect result?
asked
Nov 4, 2016
in
Algorithms
by
vaishali jhalani
Boss
(
7.1k
points)

204
views
algorithms
dijkstrasalgorithm
graphalgorithms
shortestpath
+4
votes
2
answers
27
shortest path
asked
Oct 26, 2016
in
Algorithms
by
jenny101
Active
(
1.6k
points)

164
views
shortestpath
graphalgorithms
algorithms
+2
votes
1
answer
28
Shortest path length
asked
Oct 26, 2016
in
Algorithms
by
jenny101
Active
(
1.6k
points)

123
views
graphalgorithms
shortestpath
+14
votes
2
answers
29
MADE EASY TEST
For the graph given below Dijkstra's algorithm does not provide correct shortest path tree. Suppose a new graph that is different only in weight between Q to S is created. The number of values of edge [Q to S] that ensures that Dijkstra's provide the correct ... tree where the values of edge (Q to S) ∈ [20, 20] and P' is the source vertex are ______.
asked
Sep 24, 2016
in
Algorithms
by
User007
Active
(
2.4k
points)

651
views
algorithms
shortestpath
madeeasytestseries
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
Dream of M.Tech in IIT
M.Tech preparation
My success story
IIITH Application Form
Another failure attempt
Follow @csegate
Gatecse
Recent questions tagged shortestpath
Recent Blog Comments
Many Congratulations to you and well said. When I ...
Congratulations bhava.. :) Hope we meet at IIT ...
check for what u get in the college predictor of ...
Thank You so much for the edits and making this ...
@Sunny Mukherjee Congratulations and all the best ...
34,170
questions
40,846
answers
115,884
comments
39,703
users