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
6
votes
1
answer
1
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 51
Consider a directed graph $G$ with a source vertex $s, a$ destination $t$, and nonnegative edge lengths. Under what conditions is the shortest $s-t$ path guaranteed to be unique? When all edge lengths are distinct positive ... no directed cycles. When all edge lengths are distinct powers of $2.$ None of the other options are correct.
GO Classes
asked
in
Algorithms
Jan 13
by
GO Classes
400
views
goclasses2024-mockgate-11
goclasses
algorithms
graph-algorithm
shortest-path
2-marks
0
votes
1
answer
2
algorithms
Let G1 (V, E) be a connected undirected graph and G2 (V1, E') be the subgraph of G1. Weights are assigned to the edges of G1. W(e) = 0; if e belongs to E' = 1 , otherwise. Single source shortest path algorithms is applied on G1 ... all pair of vertices and stored in a matrix. What will be additional time complexity (strict upper bound) to determine if G2 is connected or not.
24aaaa23
asked
in
Algorithms
Oct 1, 2023
by
24aaaa23
246
views
algorithms
shortest-path
time-complexity
0
votes
0
answers
3
Consider the following strategy to convert an undirected graph with negative edge weights to one that does not have negative edge weights. Let the maximum magnitude negative edge weight in the graph be -k. Then, for each edge in the graph with weight w, update the weight to w+k+1. Consider the following claim: To solve the shortest path problem in the original graph, we can run Dijkstra's algorithm on the modified graph and subtract the added weights to get the original distances. Which of the following is not correct. The claim is not true in general. The claim is not true in general for graphs with cycles. The claim is true for connected acyclic graphs. The claim is true for all graphs.
sonalrawat
asked
in
Algorithms
Aug 21, 2023
by
sonalrawat
306
views
dijkstras-algorithm
shortest-path
2
votes
1
answer
4
GO Classes 2023 | IIITH Mock Test 1 | Question: 10
$\text{G}$ is a directed graph with negative weight edges but NO negative weight cycles. Which of the following hold for Dijkstra's algorithm on $\text{G}:$ Dijkstra's algo will always give the correct output since there is no ... if we add large positive weight to every edge then it will work. Dijkstra's algo may not terminate in this case.
GO Classes
asked
in
Algorithms
Mar 26, 2023
by
GO Classes
549
views
goclasses2023-iiith-mock-1
goclasses
algorithms
dijkstras-algorithm
shortest-path
1-mark
0
votes
1
answer
5
Testbook CN question
Which of the following statement is/are incorrect about the Routing Information Protocol (RIP) protocol and Open Shortest Path First (OSPF) protocol? RIP packets are sent using TCP. OSPF packets are sent using TCP. RIP is an Network Layer protocol OSPF is an Application Layer protocol
Sahil_Lather
asked
in
Computer Networks
Jan 26, 2023
by
Sahil_Lather
492
views
computer-networks
network-layer
application-layer
shortest-path
1
vote
1
answer
6
Dijkstra's algorithm | Negative Weight Cycle
If a -ve weight cycle is reachable from source, the Dijkstra's algorithm gets into an infinite loop TRUE FALSE
Souvik33
asked
in
Algorithms
Dec 19, 2022
by
Souvik33
673
views
dijkstras-algorithm
graph-algorithm
shortest-path
1
vote
0
answers
7
TIFR CSE 2022 | Part B | Question: 13
Consider a directed graph $G=(V, E)$, where each edge $e \in E$ has a positive edge weight $c_e$. Determine the appropriate choices for the blanks below so that the value of the following linear program is the length of the shortest directed path in $G$ from $s$ ... $\text{blank }1: \min, \text{blank }2:\; \geq$ $\text{blank }1: \min, \text{blank }2:\; =$
admin
asked
in
Algorithms
Sep 1, 2022
by
admin
278
views
tifr2022
algorithms
shortest-path
0
votes
2
answers
8
Made Easy Test Series
Which of the following can be the best algorithm(s) for all pair of the shortest path problem? I. ‘V’ invocations of Dijkstra algorithm ⇒ Ο(VE logV). II. ‘V’ invocations of Bellman-Ford algorithm ⇒ Ο(V2 E). III. ‘1’ invocations of Floyd-Warshall algorithm ⇒ Ο(V3).
LRU
asked
in
Algorithms
Jan 8, 2022
by
LRU
357
views
made-easy-test-series
shortest-path
time-complexity
0
votes
1
answer
9
Nptel Assignment Question
Consider the following strategy to convert a graph with negative edge weights to one that does not have negative edge weights. Let the maximum magnitude negative edge weight in the graph be -k. Then, for each edge in the graph with weight w, ... all graphs. The claim is true for connected acyclic graphs. The claim is not true in general for connected graphs with cycles
rsansiya111
asked
in
Algorithms
Dec 8, 2021
by
rsansiya111
1.0k
views
nptel-quiz
dijkstras-algorithm
shortest-path
graph-theory
0
votes
1
answer
10
NPTEL Assignment Question
Consider the following strategy to solve the single source shortest path problem with edge weights from source s. 1. Replace each edge with weight w by w edges of weight 1 connected by new intermediate nodes 2. Run BFS(s) on the modified graph to ... ;s algorithm.s st This strategy will not solve the problem correctly. This strategy will only work if the graph is acyclic.
rsansiya111
asked
in
Algorithms
Dec 8, 2021
by
rsansiya111
1.2k
views
nptel-quiz
shortest-path
graph-search
graph-algorithm
0
votes
1
answer
11
NPTEL Assignment Question
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE? P: Minimum spanning tree of G does not change Q: Shortest path between any pair of vertices does not change P only Q only Neither P nor Q Both P and Q
rsansiya111
asked
in
Algorithms
Dec 7, 2021
by
rsansiya111
584
views
nptel-quiz
graph-algorithm
minimum-spanning-tree
shortest-path
0
votes
1
answer
12
NPTEL Assignment Question
rsansiya111
asked
in
Algorithms
Dec 7, 2021
by
rsansiya111
389
views
nptel-quiz
shortest-path
graph-algorithm
Page:
1
2
3
4
next »
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
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
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent questions tagged shortest-path
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...