How does the Dijkstra Algorithm handle graphs with unreachable vertices?

The Dijkstra Algorithm is a popular algorithm used to find the shortest path between two vertices in a graph. When it comes to handling graphs with unreachable vertices, the Dijkstra Algorithm follows a specific approach.

In the Dijkstra Algorithm, the graph is represented as a collection of vertices and edges. Each vertex is assigned a tentative distance value, which represents the current shortest distance from the source vertex to that particular vertex. Initially, the tentative distance value of the source vertex is set to 0, and all other vertices are set to infinity.

The algorithm iteratively selects the vertex with the smallest tentative distance value and explores its neighboring vertices. For each neighboring vertex, the algorithm updates its tentative distance value if a shorter path is found. This process continues until all vertices have been visited or until the destination vertex is reached.

Now, when it comes to handling graphs with unreachable vertices, the Dijkstra Algorithm handles them in the following way:

1. Initialization: The algorithm initializes all vertices with a tentative distance value of infinity, except for the source vertex, which is set to 0. This means that any unreachable vertices will remain with the initial value of infinity.

2. Exploration: During the exploration phase, the algorithm selects the vertex with the smallest tentative distance value. If this vertex is unreachable (i.e., its tentative distance value remains infinity), the algorithm terminates as it indicates that there is no path from the source vertex to any remaining vertices.

3. Termination: Once the algorithm terminates, the tentative distance values of all reachable vertices will represent the shortest path from the source vertex. Unreachable vertices will still have a tentative distance value of infinity, indicating that there is no path from the source vertex to those vertices.

In summary, the Dijkstra Algorithm handles graphs with unreachable vertices by assigning them an initial tentative distance value of infinity. During the exploration phase, if a vertex remains unreachable (i.e., its tentative distance value remains infinity), the algorithm terminates, indicating that there is no path from the source vertex to those vertices.