Recent questions tagged shortest-path / GATE Overflow for GATE CSE

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.

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...

GO Classes

465 views

GO Classes asked Jan 13

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.

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 , o...

24aaaa23

264 views

24aaaa23 asked Oct 1, 2023

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

365 views

sonalrawat asked Aug 21, 2023

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.

$\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...

GO Classes

702 views

GO Classes asked Mar 26, 2023

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

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 ...

Sahil_Lather

515 views

Sahil_Lather asked Jan 26, 2023

1 votes

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

If a -ve weight cycle is reachable from source, the Dijkstra's algorithm gets into an infinite loop TRUEFALSE

Souvik33

697 views

Souvik33 asked Dec 19, 2022

1 votes

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:\; =$

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...

admin

290 views

admin asked Sep 1, 2022

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).

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’ inv...

LRU

374 views

LRU asked Jan 8, 2022

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

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 wei...

rsansiya111

1.2k views

rsansiya111 asked Dec 8, 2021

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.

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...

rsansiya111

1.3k views

rsansiya111 asked Dec 8, 2021

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

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 statem...

rsansiya111

610 views

rsansiya111 asked Dec 7, 2021

0 votes

1 answer

12

NPTEL Assignment Question

rsansiya111

404 views

rsansiya111 asked Dec 7, 2021

3 votes

1 answer

13

GATE Overflow Test Series | Algorithms | Test 2 | Question: 1
In an undirected graph with all edge weights equal, the shortest path from a node $s$ to every other node is computed most efficiently, in terms of time complexity by $\_\_\_\_\_\_\_$. Dijkstra's algorithm with $s$ ... -Ford algorithm with $s$ as the start node Performing a DFS starting from $s$ Performing a BFS starting from $s$

In an undirected graph with all edge weights equal, the shortest path from a node $s$ to every other node is computed most efficiently, in terms of time complexity by $\_...

gatecse

262 views

gatecse asked Sep 7, 2020

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