Routing Protocols MCQs

Which algorithm is most commonly used for finding the single-source shortest path in a weighted graph with non-negative weights?

• Bellman-Ford

• Dijkstra's algorithm

• Floyd-Warshall

• Kruskal's algorithm

Bellman-Ford algorithm can handle:

• Only positive weights

• Positive and negative weights (no negative cycles)

• Only negative weights

• Zero-weight edges only

The time complexity of Dijkstra's algorithm with a binary heap is:

• O(V²)

• O(E + V log V)

• O(V log E)

• O(E log E)

Which algorithm finds shortest paths between all pairs of vertices?

• Prim's

• Dijkstra's

• Floyd-Warshall

• Bellman-Ford

Relaxation in shortest path algorithms means:

• Ignoring edges

• Updating a distance estimate if a shorter path is found

• Removing cycles

• Pausing computation

The output of a shortest path algorithm is typically a:

• Spanning tree

• Routing table

• Flow network

• Hamiltonian cycle

A negative cycle in a graph implies:

• Multiple optimal solutions

• No well-defined shortest path

• Minimum spanning tree is impossible

• Faster convergence

In a weighted graph, edges can represent:

• Only physical distance

• Any cost metric such as delay or bandwidth

• CPU usage

• File size

Distance vector protocols exchange:

• Complete topology maps

• Vectors of destination distances to neighbors

• Only default routes

• Encryption keys

A well-known distance vector protocol for IP networks is:

• OSPF

• RIP

• IS-IS

• BGP (core mode)