Log In
3 votes

Algorithm which solves the all pair shortest path problem is

A)Dijkstra's algorithm

B)Floyd's algorith

C)Prim's algorithmm

D)Warshall's algorithm

in DS 4.2k views

2 Answers

5 votes
A)Dijkstra->>Single Source Shortest Path

C) Prims->>To obtain Minimum Spanning Tree

B&D) Floyd-Warshall Algo->>All pair Shortest path

Robert Floyd & Stephen Warshall two scientist :-from there name a single dynamic algorithm Floyd-Warshall...(Note:-they are not 2 different algorithms.. So, they should not given in two options)
0 votes
you give options wrong because floyd's and warshall's are not two different algorithms . floyd-warshall algorithm is used to find the all pair shortest path problem.

Related questions

3 votes
2 answers
Let P be a shortest path from some vertex s to some other vertex t in a directed graph. If the weight of each edge in the graph is increased by one, P will still be a shortest path from s to t. T/F
asked Dec 6, 2016 in Algorithms dd 722 views
1 vote
0 answers
TRUE / FALSE Explain Please.. An undirected graph is said to be Hamiltonian if it has a cycle containing all the vertices. Any DFS tree on a Hamiltonian graph must have depth V − 1.
asked Jul 31, 2018 in Algorithms Rishav Kumar Singh 220 views
0 votes
0 answers
I have a small doubt. Chapter 25 All pairs shortest path of CLRS says following: To solve the all-pairs shortest-paths problem on an input adjacency matrix, we need to compute not only the shortest-path weights but also a predecessor matrix $\Pi=(\pi_{ij})$, where $\pi_{ij}$ ... $i$ and predecessor subgraph of $G$ for $i$) the same?
asked Mar 24, 2018 in Programming GateAspirant999 116 views