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
91
why do we run bellman-ford algorithm n-1 times ?
I am unable to get the logic behind running bellman-ford for n-1 times , I have already gone through this link , but still couldn't get it clearly . http://cs.stackexchange.com/questions/50557/why-do-we-need-to-run-the-bellman-ford-algorithm-for-n-1-times
radha gogia
asked
in
Algorithms
Dec 20, 2015
by
radha gogia
2.8k
views
algorithms
bellman-ford
shortest-path
0
votes
1
answer
92
algo
if all edge in the graph have distinct weight the the sortest path between two vertex is unique?/
Chandra Bhushan Kuma
asked
in
Algorithms
Dec 19, 2015
by
Chandra Bhushan Kuma
151
views
graph-algorithms
shortest-path
1
vote
1
answer
93
Algorithms:Which of the following statements is/are true?
Which of the following statements is/are true? S1: Dijkstra's algorithm is not affected by negative edge weight cycles in the graph and gives correct shortest path. S2: Bellman ford algorithm finds all negative edge weight cycles present in the graph. a) ... Only S1 c) Both S1 and S2 d) Neither S1 and nor S2 Ans) D how ? But My ans only s2
Prasanna
asked
in
Algorithms
Nov 29, 2015
by
Prasanna
4.1k
views
dijkstras-algorithm
bellman-ford
shortest-path
2
votes
1
answer
94
Do Prim’s and Kruskal’s algorithms still work if the edge weights are allowed to be negative?
yes
asked
in
Algorithms
Oct 13, 2015
by
yes
3.9k
views
shortest-path
graph-algorithms
minimum-spanning-tree
5
votes
1
answer
95
dijkstra's algo
yes
asked
in
Algorithms
Oct 12, 2015
by
yes
526
views
graph-algorithms
shortest-path
0
votes
1
answer
96
Path matrix
given a graph G,a matrix Pk represent a matrix in which each entry pk[i][j] represent the shortest path from node i to node j in G which uses only nodes 1,2,3.............k-1 .The corresponding graph formed by using matrix Pk[i][j] is termed as ... .now my question is how to find Gk if the graph G is represented by using adjacency list and what will be the time complexity to do it ??
Saurav
asked
in
Algorithms
Aug 27, 2015
by
Saurav
557
views
graph-theory
shortest-path
time-complexity
0
votes
1
answer
97
Do we categorize all optimization problems in NP ?
I just want to confirm whether all optimization problems are in NP or not say to find the shortest path this can be done in polynomial time and If I am given a graph and I have to find whether there exists any path ... problem ,so is it that the optimization version of a problem is polynomial solvable and its similar decision version is NP.
radha gogia
asked
in
Algorithms
Jul 18, 2015
by
radha gogia
227
views
p-np-npc-nph
shortest-path
time-complexity
0
votes
2
answers
98
Can we modify Dijkstra algorithm for computing maximum distance problem
Following statement is true or false? If we make following changes to Dijkstra, then it can be used to find the longest simple path, assume that the graph is acyclic. 1) Initialize all distances as minus infinite instead of ... with minus infinty so then maximum can be found , so then whats the issue why cant we finalize it ?
radha gogia
asked
in
Algorithms
Jul 5, 2015
by
radha gogia
1.9k
views
dijkstras-algorithm
true-false
graph-algorithms
shortest-path
2
votes
2
answers
99
In bellman ford algo why are the no of passes |V|-1 ?
Bellman-ford algo 1) This step initializes distances from source to all vertices as infinite and distance to source itself as 0. Create an array dist[] of size |V| with all values as infinite except dist[src] where src is source vertex. 2) This step ... + weight of edge uv, then update dist[v] .dist[v] = dist[u] + weight of edge uv
radha gogia
asked
in
Algorithms
Jul 5, 2015
by
radha gogia
1.7k
views
bellman-ford
shortest-path
0
votes
2
answers
100
How to solve below question of undirected subgraph for finding shortest path ?
Let G = (V, E) be an undirected graph with a subgraph G1 = (V1, E1). Weights are assigned to edges of G as follows : w(e) = 0 if e belongs to E1 1 otherwise A single-source shortest path algorithm is executed on the weighted ... B) G1 is connected (C) V1 forms a clique in G (D) G1 is a tree Plz tell the approach........
radha gogia
asked
in
Algorithms
Jul 4, 2015
by
radha gogia
929
views
graph-algorithms
shortest-path
2
votes
1
answer
101
Dijkstra shorest path algorithm
if Dijkstra shorest path algorithm takes 8 second for a graph of 1000 nodes then approximatly how much time would it take for a graph of 1000000 nodes. a) 8000000 sec. b) 8000 sec. c) 16000 sec. d)16000000 sec.
Sahil Gupta
asked
in
Algorithms
Dec 16, 2014
by
Sahil Gupta
424
views
dijkstras-algorithm
shortest-path
time-complexity
Page:
« prev
1
2
3
4
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 ☺️☺️....