Question

What are some applications where it is necessary to find the length of a longest simple path between two vertices in a weighted graph?

Short answer

Circuit checking process, sightseeing tour.

Step-by-step solution

Given data

Tour covering two cities (vertices).

Concept used of Dijkstra’s algorithm

Dijkstra's algorithm allows us to find the longest path between any two vertices of a graph.

Find the practical instances

In a sightseeing tour covering two cities (vertices) one may be interested in visiting all the tourist spots in the neighborhood, which may entail finding the longest path between the cities. In a circuit checking process, one is interested in covering all the intermediate connections which results in finding the longest paths between the nodes.

The longer the path, more nodes and hence more interconnections are checked.