GATE CS 2008 Q45 — Shortest Paths (Dijkstra, Bellman-Ford)

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 complexity of the fastest algorithm to find the lengths of shortest paths from $s$ to all vertices that are reachable from $s$ in ${G}?$

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 of $d(u, v), u, v \in V$ such that $u \neq v$, be $30$. Let $T$ be any breadth-first-search tree of $G$. Which ONE of the given options is CORRECT …

Let $G = (V,E)$ be a directed, weighted graph with weight function $w: E \rightarrow \mathbb{R}$. For some function $f: V \rightarrow \mathbb{R}$, for each edge$(u,v)\in E$, define ${w}'(u,v)$ as $w(u,v)+f(u)-f(v)$. Which one of the options completes the following sentence so that it is TRUE? “The shortest paths in $G$ under $w$ are shortest …

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

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

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