Test: Shortest Paths - Computer Science Engineering (CSE) MCQ

See Dijkstra’s shortest path algorithm When the algorithm reaches vertex 'C', the distance values of 'D' and 'E' would be 7 and 6 respectively. So the next picked vertex would be 'E'

The shortest path in an un-weighted graph means the smallest number of edges that must be traversed in order to reach the destination in the graph. This is the same problem as solving the weighted version where all the weights happen to be 1. If we use Queue (FIFO) instead of Priority Queue (Min Heap), we get the shortest path in linear time O(|V| + |E|). Basically we do BFS traversal of the graph to get the shortest paths.

Dijkstra’s single source shortest path is not guaranteed to work for graphs with negative weight edges, but it works for the given graph. Let us see... Let us run the 1st pass b 1 b is minimum, so shortest distance to b is 1. After 1st pass, distances are c 3, e -2. e is minimum, so shortest distance to e is -2 After 2nd pass, distances are c 3, f 0. f is minimum, so shortest distance to f is 0 After 3rd pass, distances are c 3, g 3. Both are same, let us take g. so shortest distance to g is 3. After 4th pass, distances are c 3, h 5 c is minimum, so shortest distance to c is 3 After 5th pass, distances are h -2 h is minimum, so shortest distance to h is -2

* Time Comlexity of the Dijkstra’s algorithm is O(|V|^2 + E)
* Time Comlexity of the Warshall’s algorithm is O(|V|^3) *
DFS cannot be used for finding shortest paths
* BFS can be used for unweighted graphs. Time Complexity for BFS is O(|E| + |V|)

Time complexity of Bellman-Ford algorithm is θ(VE) where V is number of vertices and E is number edges (See this). If the graph is complete, the value of E becomes θ(V^2). So overall time complexity becomes θ(V^3)

See the following counterexample. There are 4 edges s-a, a-b, b-t and s-t of wights 1, 1, 1 and 4 respectively. The shortest path from s to t is s-a, a-b, b-t. IF we increase weight of every edge by 1, the shortest path changes to s-t.

In shortest path algo, we pick the minimum distance vertex from the set of vertices for which distance is not finalized yet. And we finalize the distance of the minimum distance vertex. For maximum distance problem, we cannot finalize the distance because there can be a longer path through not yet finalized vertices.

Using Topological Sort, we can find single source shortest paths in O(V+E) time which is the most efficient algorithm. See following for details. Shortest Path in Directed Acyclic Graph

With BFS, we first find explore vertices at one edge distance, then all vertices at 2 edge distance, and so on.

The shortest path remains same. It is like if we change unit of distance from meter to kilo meter, the shortest paths don't change.

Dijkstra is a greedy algorithm where we pick the minimum distant vertex from not yet finalized vertices. Bellman Ford and Floyd Warshell both are Dynamic Programming algorithms where we build the shortest paths in bottom up manner.

There can be more than one paths with same weight. Consider a path with one edge of weight 5 and another path with two edges of weights 2 and 3. Both paths have same weights.

Dijkstra and Bellman-Ford both work fine for a graph with all positive weights, but they are different algorithms and may pick different edges for shortest paths.

Bellman-Ford shortest path algorithm is a single source shortest path algorithm. So it can only find cycles which are reachable from a given source, not any negative weight cycle. Consider a disconnected where a negative weight cycle is not reachable from the source at all. If there is a negative weight cycle, then it will appear in shortest path as the negative weight cycle will always form a shorter path when iterated through the cycle again and again.

When shortest path shortest path from v1 (one of the vertices in V1) is computed. G1 is connected if the distance from v1 to any other vertex in V1 is greater than 0, otherwise G1 is disconnected.

In the original input matrix, A[j , k] is 1 if there is an edge from j to k, else 0.
Below expression is important to note:
A[j, k] = max(A[j, k] (A[j, i] + A [i, k]);
This expression puts the count of maximum edges on a path from j to k. In this expression, we consider every vertex k that can become an intermediate vertex and can give longer path.

Note that the given graph is undirected, so an edge (u, v) also means (v, u) is also an edge. Since a shorter path can always be obtained by using edge (u, v) or (v, u), the difference between d(u) and d(v) can not be more than 1.

The task is to find minimum number of edges in a path in G from vertex 1 to vertex 100 such that we can move to either i+1 or 3i from a vertex i.
Since the task is to minimize number of edges, we would prefer to follow 3*i.
Let us follow multiple of 3.

1 => 3 => 9 => 27 => 81, now we can't follow multiple of 3. So we will have to follow i+1. This solution gives a long path.

What if we begin from end, and we reduce by 1 if the value is not multiple of 3, else we divide by 3.
100 => 99 => 33 => 11 => 10 => 9 => 3 => 1

So we need total 7 edges.