Recent questions tagged shortest-path

Consider two statements $\text{S1}$ and $\text{S2}.$$\text{S1}:$ To find a shortest path for a graph with negative weights, we can eliminate negative edges by adding the ...

Consider two statements $\text{S1}$ and $\text{S2}$.$\text{S1}:$ To solve the single-source-shortest-paths (SSSP) problem for a graph with no negative-weight edges, it is...

Which of the following is/are FALSE?Let $\text{G = (V, E)}$ be a weighted graph and let $\text{M}$ be a minimum spanning tree of $\text{G}$. The path in $\text{M}$ betwee...

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

Given an undirected, weighted graph $\mathrm{G}$ with positive, integer edge weights, we want to find a path shortest path from $u$ to $v$ with the below condition.The co...

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

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

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

Consider a weighted directed graph. The current shortest distance from source $S$ to node $x$ is represented by $d[x]$. Let $d[v] =29$, $d[u]=15$, $w[u,v]=12$. What is th...

When using Dijkstra’s algorithm to find shortest path in a graph, which of the following statement is not true?It can find shortest path within the same graph data struct...

The time required to find the shortest path in a graph with $n$ vertices and $e$ edges is:$O(e)$$O(n)$$O(e^{2})$$O(n^{2})$

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