Match the following: (A) Floyd Warshall (i) shortest path between two vertices…

Concept

A graph problem fixes which shortest-path or tree algorithm fits. Three families decide every match: an all-pairs shortest-path algorithm finds the shortest distance between every ordered pair of vertices at once; a single-source shortest-path algorithm fixes one source and finds shortest paths from it to all others (and so also to any one target vertex); and a minimum-spanning-tree algorithm connects all vertices with minimum total edge weight, which is not a shortest-path task at all.

Applying it to each item

1. Floyd-Warshall runs a dynamic program over all intermediate vertices, so it returns shortest distances for every pair simultaneously - it is the all-pairs shortest path algorithm, matching "solving all pair shortest path".

2. Kruskal's algorithm greedily adds the lightest safe edge without forming a cycle, building a minimum-weight tree that spans all vertices - it matches "Minimum spanning tree".

3. Bellman-Ford relaxes all edges from a single chosen source and also handles negative edge weights - it matches "single source shortest path".

4. Dijkstra is also a single-source method (for non-negative weights), but in this forced one-to-one matching the "single source shortest path" target is already taken by Bellman-Ford, so Dijkstra takes the remaining "shortest path between two vertices" - which it can do by stopping once the target vertex is settled.

Cross-check

Only one assignment makes every pairing factually defensible at once: Floyd-Warshall = all-pairs, Kruskal = MST, Bellman-Ford = single-source, Dijkstra = path between two vertices. Any pairing that calls Floyd-Warshall a two-vertex method, or makes Bellman-Ford all-pairs, or links Dijkstra to a spanning tree, breaks on a definition, so the matching above is the consistent one.