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
1
vote
2
answers
61
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.
Shyam Singh 1
asked
in
Algorithms
May 8, 2017
by
Shyam Singh 1
1.1k
views
shortest-path
2
votes
4
answers
62
Bellman Ford Shortest path
Is the below statement correct: Bellman Ford finds all negative weight cycles in the graph. This is true or false?
Bongbirdie
asked
in
Algorithms
Apr 7, 2017
by
Bongbirdie
1.4k
views
algorithms
shortest-path
bellman-ford
true-false
2
votes
1
answer
63
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!?
Bongbirdie
asked
in
Algorithms
Apr 7, 2017
by
Bongbirdie
630
views
shortest-path
bellman-ford
algorithms
1
vote
1
answer
64
#Totally Confused# please tell Using Dijkstra Algorithm solve shortest path algorithm from A to D.
Using DIjkstra algorithm solve shortest path algorithm from A to D
LavTheRawkstar
asked
in
Computer Networks
Apr 6, 2017
by
LavTheRawkstar
706
views
algorithms
shortest-path
dijkstras-algorithm
computer-networks
0
votes
0
answers
65
Calculate the shortest path using TSP Greedy Appraoch
Calculate the shortest path using TSP Greedy Appraoch
LavTheRawkstar
asked
in
Algorithms
Mar 26, 2017
by
LavTheRawkstar
278
views
algorithms
shortest-path
5
votes
1
answer
66
Testbook live Testseries
Which of the following statements are false ? $1.$ A depth-first search of a directed graph always produces the same number of tree edges (i.e., independent of the order in which the vertices are provided and independent of the order of the ... between any two vertices will not change. $4.$ Dijkstra's algorithm may not terminate if the graph contains negative weight edges.
Akriti sood
asked
in
Algorithms
Jan 23, 2017
by
Akriti sood
1.3k
views
graph-search
shortest-path
testbook-test-series
0
votes
1
answer
67
Test by Bikram | Mock GATE | Test 1 | Question: 42
Find the missing statement in the if loop of $Floyd$ algorithm. Procedure Floyd: (var A: array[1...n,1...n] of real; C: array [1...n,1...n] of real); Var i, j, k: integer; begin M for i:=l to n do for j:=l to n do A[i,j]: =C[i,j] for i:=l to n do A[i,j ]:=0 ; ... $A[i,j]: = A[i, j] + A[k,j]$ $A[i,j]: = A[j,k]+ A[j,i]$ $A[i,j]: =A[i,k] + A[i,j]$
Bikram
asked
in
GATE
Jan 16, 2017
by
Bikram
199
views
tbb-mockgate-1
algorithms
graph-algorithms
shortest-path
0
votes
3
answers
68
Ace Test Series
Vignesh Kamath
asked
in
Algorithms
Jan 14, 2017
by
Vignesh Kamath
864
views
algorithms
shortest-path
ace-test-series
0
votes
2
answers
69
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)$
go_editor
asked
in
Graph Theory
Dec 30, 2016
by
go_editor
538
views
cmi2016
graph-theory
shortest-path
1
vote
2
answers
70
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
go_editor
asked
in
Graph Theory
Dec 30, 2016
by
go_editor
724
views
cmi2016
graph-theory
shortest-path
1
vote
1
answer
71
MadeEasy Test Series: Algorithms - Graph Algorithms
rahul sharma 5
asked
in
Algorithms
Dec 14, 2016
by
rahul sharma 5
729
views
made-easy-test-series
algorithms
graph-algorithms
shortest-path
dijkstras-algorithm
3
votes
2
answers
72
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
dd
asked
in
Algorithms
Dec 6, 2016
by
dd
1.8k
views
graph-algorithms
shortest-path
graph-theory
0
votes
1
answer
73
cormen
what will be the effect if we take equality in relaxaction condition of bellman ford algo??
2018
asked
in
Algorithms
Nov 29, 2016
by
2018
127
views
bellman-ford
shortest-path
descriptive
1
vote
3
answers
74
Find shortest path
Rakesh K
asked
in
Algorithms
Nov 27, 2016
by
Rakesh K
2.3k
views
algorithms
graph-algorithms
shortest-path
test-series
0
votes
8
answers
75
MadeEasy Test Series: Algorithms - Shortest Paths
Consider the following statements For every weighted graph and any two vertices $s$ and $t$, Bellman-Ford algorithm starting at $s$ will always return the shortest path to $t$. At the termination of the Bellman-ford algorithm, ... shortest path is found for a vertex for which shortest path is well-defined. Which of the above statements are true?
vaishali jhalani
asked
in
Algorithms
Nov 6, 2016
by
vaishali jhalani
2.7k
views
made-easy-test-series
algorithms
shortest-path
descriptive
6
votes
1
answer
76
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)?
vaishali jhalani
asked
in
Algorithms
Nov 5, 2016
by
vaishali jhalani
2.5k
views
algorithms
dijkstras-algorithm
graph-algorithms
shortest-path
2
votes
1
answer
77
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.
vaishali jhalani
asked
in
Algorithms
Nov 5, 2016
by
vaishali jhalani
482
views
algorithms
shortest-path
1
vote
1
answer
78
Dijkstra's Agorithm
When the graph contain negetive weight edges but no negetive weight cycle, in this case can dijkstra leads to incorrect result?
vaishali jhalani
asked
in
Algorithms
Nov 4, 2016
by
vaishali jhalani
847
views
algorithms
dijkstras-algorithm
graph-algorithms
shortest-path
5
votes
2
answers
79
shortest path
jenny101
asked
in
Algorithms
Oct 26, 2016
by
jenny101
928
views
shortest-path
graph-algorithms
algorithms
test-series
2
votes
1
answer
80
Shortest path length
jenny101
asked
in
Algorithms
Oct 26, 2016
by
jenny101
371
views
graph-algorithms
shortest-path
test-series
3
votes
2
answers
81
GATE Overflow | Algorithms | Test 1 | Question: 22
Consider the below statements: Adding a constant to every edge weight does not change the solution to the single-source shortest-paths problem. Adding a constant to every edge weight does not change the solution to the minimum spanning tree problem. 1 is FALSE 2 is TRUE 1 is TRUE 2 is FALSE Both 1 and 2 are TRUE Both 1 and 2 are FALSE
Bikram
asked
in
Algorithms
Oct 4, 2016
by
Bikram
333
views
go-alogrithms-1
algorithms
minimum-spanning-tree
shortest-path
17
votes
1
answer
82
MadeEasy Test Series: Algorithms - Graph Algorithms
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 ... tree where the values of edge (Q to S) ∈ [-20, 20] and P' is the source vertex are ______.
User007
asked
in
Algorithms
Sep 24, 2016
by
User007
2.0k
views
made-easy-test-series
algorithms
graph-algorithms
shortest-path
dijkstras-algorithm
3
votes
1
answer
83
UGC NET CSE | Junet 2015 | Part 3 | Question: 31
An all-pairs shortest-paths problem is efficiently solved using: Dijkstra's algorithm Bellman-Ford algorithm Kruskal algorithm Floyd-Warshall algorithm
go_editor
asked
in
Algorithms
Aug 1, 2016
by
go_editor
2.5k
views
ugcnetcse-june2015-paper3
algorithms
shortest-path
1
vote
1
answer
84
UGC NET CSE | December 2014 | Part 3 | Question: 34
Dijkstra algorithm, which solves the single-source shortest--paths problem, is a _______, and the Floyd-Warshall algorithm, which finds shortest paths between all pairs of vertices, is a ________. ... Divide-conquer algorithm, Greedy algorithm Greedy algorithm, Dynamic programming algorithm Dynamic programming algorithm, Greedy algorithm
makhdoom ghaya
asked
in
Algorithms
Jul 28, 2016
by
makhdoom ghaya
2.8k
views
ugcnetcse-dec2014-paper3
algorithms
shortest-path
1
vote
0
answers
85
Test serise qn=2
Here I have doubt which one is stronger ans option(A) or (D)?.According to question op(A) & (D) gives same output.I think op(D) is stronger ans why bez |v|-1 means |E| no. of edges must(according to question max path length) but |E| not always |V|-1. -Plz give the correct reason by Arjun Suresh sir-
dileswar sahu
asked
in
Algorithms
Jul 25, 2016
by
dileswar sahu
324
views
algorithms
graph-algorithms
shortest-path
3
votes
2
answers
86
BFS
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 s and a is atmost one more than the number of edges on ... and b. 3. There is a path between a and b. a.1 only b.1 and 2 only c. 2 only d. 1, 2 and 3
gshivam63
asked
in
Algorithms
Jul 25, 2016
by
gshivam63
17.3k
views
algorithms
breadth-first-search
shortest-path
1
vote
1
answer
87
Self Made
If a graph contains a positive weight cycle reachable from source, Can we find a well defined shortest path using Dijkstra/Bellman-Ford algorithm?
Jithin Jayan
asked
in
Algorithms
Jul 23, 2016
by
Jithin Jayan
157
views
greedy-algorithm
dijkstras-algorithm
bellman-ford
shortest-path
descriptive
4
votes
2
answers
88
Is Bellman Ford Dynamic Programming approach ?
Is bellman ford a dynamic programming approach? If yes, what is the reason behind it? How do we find an optimal substructure and overlapping sub problems in this ?
Khyati Tuli
asked
in
Algorithms
Jul 22, 2016
by
Khyati Tuli
8.1k
views
algorithms
shortest-path
graph-algorithms
4
votes
1
answer
89
Bellman Ford Variation in Data Structures, tricky test ?
We have a Directed Graph with 100 vertexes. v1 --> v2 --> ... v100 and all edges weights is equal to 1. we want to used bellman-ford for finding all shortest paths from v1 to other vertexes. this algorithm in each ... and maximum of steps in this problem? ُSolution says 2 and 100. anyone can say how the min and max steps is calculated?
Sara Nimlon
asked
in
DS
Jul 10, 2016
by
Sara Nimlon
856
views
algorithms
data-structures
graph-algorithms
shortest-path
11
votes
3
answers
90
ISRO2007-80
Djikstra’s algorithm is used to Create LSAs Flood an internet with information Calculate the routing tables Create a link state database
go_editor
asked
in
Algorithms
Jun 10, 2016
by
go_editor
4.3k
views
isro2007
algorithms
graph-algorithms
shortest-path
dijkstras-algorithm
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
Life happens, just chill and do hardwork
ISRO RECRUITMENT FOR SCIENTIST B THROUGH GATE
POWER GRID CORPORATION OF INDIA LIMITED
INSTITUTE OF BANKING PERSONNEL SELECTION
GATE Overflow books for TIFR, ISRO, UGCNET and NIELIT
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
(648)
Exam Queries
(841)
Tier 1 Placement Questions
(17)
Job Queries
(74)
Projects
(9)
Unknown Category
(854)
Recent questions tagged shortest-path
Recent Blog Comments
Please upload 4th Mock Test, due date was 4th Dec.
The counts of answered, marked etc in the exam...
Tests have been sent and all tests will be...
Maximum age limit changed from 35 yrs. to 28...
Hmm, sir totally getting your point ☺️☺️....