• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q58SE

Expert-verified
Found in: Page 738

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

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

The shortest path is f to z together.

See the step by step solution

## Step 1: 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.