GATE Computer Science Engineering(CSE) 2027 Test: Shortest Paths Free Online

Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijstra?s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.

To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:

Dijkstra’s single source shortest path algorithm when run from vertex a in the below graph, computes the correct shortest path distance to

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

Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge weighted directed graph with vertex P as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized?

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

In a weighted graph, assume that the shortest path from a source 's' to a destination 't' is correctly calculated using a shortest path algorithm. Is the following statement true? If we increase weight of every edge by 1, the shortest path always remains same.

Following statement is true or false?
If we make following changes to Dijkstra, then it can be used to find the longest simple path, assume that the graph is acyclic.

1) Initialize all distances as minus infinite instead of plus infinite.
2) Modify the relax condition in Dijkstra's algorithm to update distance of an adjacent v of the currently considered vertex u only if "dist[u]+graph[u][v] > dist[v]". In shortest path algo, the sign is opposite.

Which of the following algorithm can be used to efficiently calculate single source shortest paths in a Directed Acyclic Graph?

Given a directed graph where weight of every edge is same, we can efficiently find shortest path from a given source to destination using?

Is the following statement valid about shortest paths? Given a graph, suppose we have calculated shortest path from a source to all other vertices. If we modify the graph such that weights of all edges is becomes double of the original weight, then the shortest path remains same only the total weight of path changes.

Match the following

Group A                                                                        Group B
a) Dijkstra's single shortest path algo                      p) Dynamic Programming
b) Bellmen Ford's single shortest path algo             q) Backtracking
c) Floyd Warshell's all pair shortest path algo.         r) Greedy Algorithm

Is the following statement valid?. 

Given a weighted graph where weights of all edges are unique (no two edge have same weights), there is always a unique shortest path from a source to destination in such a graph.

Is the following statement valid?. 
Given a graph where all edges have positive weights, the shortest paths produced by Dijsktra and Bellman Ford algorithm may be different but path weight would always be same.

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 negative weighted cycle is reachable from the source.

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 complexity:

Let G = (V, E) be an undirected graph with a subgraph G1 = (V1, El). Weights are assigned to edges of G as follows :

A single-source shortest path algorithm is executed on the weighted graph (V, E, w) with an arbitrary vertex ν1 of V1 as the source. Which of the following can always be inferred from the path costs computed?

Let G (V, E) be a directed graph with n vertices. A path from v_i to v_j in G is sequence of vertices (v_i, v_i+1, ......., v_j) such that (vk, v_k+1) ∈ E for all k in i through j - 1. A simple path is a path in which no vertex appears more than once. Let A be an n x n array initialized as follow

Consider the following algorithm.

for i = 1 to n
     for j = 1 to n
         for k = 1 to n
               A [j , k] = max (A[j, k] (A[j, i] + A [i, k]);

Q. Which of the following statements is necessarily true for all j and k after terminal of the above algorithm ?

Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x ∈ V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u, v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u) – d(v)?

Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is