Question

Devise an algorithm for finding the shortest path between two vertices in a simple connected weighted graph that passes through a specified third vertex.

Short answer

The shortest path is f to z together.

Step-by-step solution

Introduction

In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.

Step 2: Find the shortest path

Let us take the shortest path from a to z that passes through say f first of all shortest path from a to f and a shortest path from f to z , then put them together. In order to find shortest path for each of them use Dijkstra’s algorithm.

Hence, put f to z together, to find the shortest path.