Shortest Path

Let $G(V, E)$ be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the numb...

Let $G$ be a weighted directed acyclic graph with $m$ edges and $n$ vertices. Given $G$ and a source vertex $s$ in $G$, which one of the following options gives the worst case time...

Let G be any undirected graph with positive edge weights, and T be a minimum spanning tree of G. For any two vertices, u and v, let d₁(u, v) and d₂(u, v) be the shortest distances...

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph G is/are TRUE?

Let G be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant $\alpha$ is added to the weight of every edge. Which ONE of the following stateme...

Let G(V, E) be an undirected and unweighted graph with 100 vertices. Let d(u, v) denote the number of edges in a shortest path between vertices u and v in V. Let the maximum value...

Let $G(V, E)$ be an undirected and unweighted graph with 100 vertices. Let $d(u, v)$ denote the number of edges in a shortest path between vertices $u$ and $v$ in $V$. Let the maxi...

Let $G$ be any undirected graph with positive edge weights, and $T$ be a minimum spanning tree of $G$. For any two vertices, $u$ and $v$, let $d_1(u, v)$ and $d_2(u, v)$ be the sho...

Let $G$ be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant $\alpha$ is added to the weight of every edge. Which ONE of the following state...

Let G = (V, E) be a directed, weighted graph with weight function w: E $$ \to $$ R. For some function f: V $$ \to $$ R, for each edge (u, v) $$ \in $$ E, define w'(u, v) as w(u, v)...

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

Consider the weighted undirected graph with $$4$$ vertices, where the weight of edge $$\left\{ {i,j} \right\}$$ is given by the entry $${W_{ij}}$$ in the matrix $$W.$$ $$$W = \left...

Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For $$x \in V$$, let d(x) denote the shortest distance in G from s to x. A breadt...

Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing

Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre specified pair...

What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?

Consider a complete undirected graph with vertex set {0,1,2,3,4}. Entry W ij in the matrix W below is the weight of the edge {i, j} $$$W = \left( {\matrix{ 0 & 1 & 8 & 1 & 4 \cr 1...

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W(ij) in the matrix W below is the weight of the edge {i, j}. $$$w = \left( {\matrix{ 0 & 1 & 8 & 1 & 4...

Which of the following statement(s) is / are correct regarding Bellman-Ford shortest path algorithm? P: Always finds a negative weighted cycle, if one exist s. Q: Finds whether any...

In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by

Consider a weighted undirected graph with positive edge weights and let $$uv$$ be an edge in the graph. It is known that the shortest path from the source vertex $$s$$ to $$u$$ has...

Let G(V, E) an undirected graph with positive edge weights. Dijkstra's single-source shortest path algorithm can be implemented using the binary heap data structure with time compl...

Let G=(V,E) be an undirected graph with a subgraph G 1 =(V 1 ,E 1 ). Weights are assigned to edges of G as follows. $$$w(e) = \begin{cases} 0 \text{, if } e \in E_1 \\1 \text{, oth...

Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r, u) and d(r, v) be the lengths of the shortest paths from r to...