Dijkstra\'s algorithm examples and answers PDF

Preview

Summary

further maths networks...

Description

DIJKSTRA’S ALGORITHM TO FIND THE SHORTEST PATH BETWEEN TWO POINTS Example 1 – Worked Example 20 (page 503 – 504) Determine the shortest path from A to E by using Dijkstra’s algorithm.

B

C

D

Example 2 Find the shortest path from A to F in the weighted graph below.

E

B

C

D

E

F

Example 3 Find the shortest path from A to F Solution can be found at: https://www.youtube.com/watch?v=db_-e07jkjo

MATRICES REVISION Question 1 Alan, Bob, Colin and David play each other in a round robin table tennis competition. The directed graph showing their match results is drawn to the right. a. Find the Dominance matrix D b. Can the players be ranked using D only? c. Find S = D + D2 and use it to fully rank the players.

Question 2 Imagine we live in a world where people can be ‘happy’, ‘neither happy nor sad’, or ‘sad’, but the way people feel can change from day to day. The transition matrix opposite shows how people’s feelings may vary from day to day in this world, and the proportion of people involved. In the transition matrix, the columns define the situation today and the rows define the situation tomorrow. On a given day, out of 2000 people, 1200 are ‘happy’, 600 are ‘neither happy nor sad’ and 200 are ‘sad’. Write down a matrix, S0, that describes this situation. a. The next day, how many people do we expect to be happy? b. After 5 days, how many people do we expect to be happy? c. In the long term, how many of the 2000 people do we expect to be happy?

ANSWERS Question 1

Question 2...