Dark Mode

Recent questions tagged shortest-path

0 votes

2 answers

1

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

by LRU

149 views

0 votes

1 answer

2

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

257 views

0 votes

1 answer

3

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

332 views

0 votes

1 answer

4

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

192 views

0 votes

1 answer

5

NPTEL Assignment Question

rsansiya111 asked in Algorithms Dec 7, 2021

146 views

6 votes

3 answers

6

CMI2018-A-4
Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$ For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ For an edge $(u,v)$ in $G,$ what can not be the value of $d(u)-d(v)?$ $2$ $-1$ $0$ $1$

gatecse asked in Graph Theory Sep 13, 2019

545 views

0 votes

1 answer

7

Made Easy Test Series:Algorithm- Minimum Weight Path
Consider the following statement: $A)$ If all edge weight of a graph are positive then any subset of edges that connect all vertices and has minimum total weight is a tree. $B)$ ... minimum weight graph?? and what about B)?? Is it just saying each minimum path between $2$ vertices makes total shortest path??

srestha asked in Algorithms May 10, 2019

323 views

0 votes

1 answer

8

Virtual Gate Test Series: Algorithms - Graphs

SameekshaGupta asked in Algorithms Jan 13, 2019

by SameekshaGupta

310 views

4 votes

1 answer

9

GATE Overflow | Mock GATE | Test 1 | Question: 47
Which of the following statements is/are correct with respect to Djikstra Algorithm? (P) It always works perfectly for graphs with negative weight edges. (Q) It does not work perfectly for graphs with negative weight cycles. (R) It may or may not work for graphs ... , S, T and U are correct Only Q, R, T are correct Only Q, R, S, T and U are correct

Ruturaj Mohanty asked in Algorithms Dec 27, 2018

by Ruturaj Mohanty

1.0k views

0 votes

0 answers

10

self doubt multistaGE GRAPH
https://gateoverflow.in/86958/find-shortest-path IN THIS QUESTION WHEN WE DO FINDING FROM END A SITUATION CAME WHERE WE HAVE TWO PATH FROM 8 OF LENGTH 3 EACH SO WHERE TO MOVE NOW AND I AM FINDING MINIMUM LENGTH 14 BUT ANSWER SAYS 15.

eyeamgj asked in Algorithms Nov 21, 2018

175 views

Page:

1
2
3
4
next »

Recent questions tagged shortest-path