Algorithms and Data Structures 2020

Week 12. Shortest Path

Algorithms and Data Structures

13 Week 12. Shortest Path

Reading 12 Goodrich & Tamassia: Chapter 14

13.1 Algorithms

Learn (1) proofs and (2) complexity for Dijkstra’s Algorithm.

Graph Algorithm Problems

1.
DFT and BFT
2.
Topological Sort
3.
Transitive Closure
4.
Shortest Path
5.
Spanning Tree

13.2 Projects and Exercises

   13.2.1 Warm-up Exercise
   13.2.2 Compulsory Assignment
   13.2.3 Exercises

13.2.1 Warm-up Exercise

pict


Figure 1: A sample graph

Problem 13.1 Consider the graph in Figure 1. Make a manual breadth first search from node A, showing the steps, and the BFS tree you end up with.

Problem 13.2 Consider the graph in Figure 1. Manually calculate the shortest paths from A using Dijkstra’s algorithm. Show the calculations and the resulting shortest path weights for each target node.

13.2.2 Compulsory Assignment

Problem 13.3 Communication networks are typically modelled as graphs. The edges represent links and the vertices relay messages. Imagine an ad hoc network set up with rather primitive equipment with low bandwidth, such as subsea links or long distance space links.

Video transmission of adequate quality is possible if the path from the sender to the receiver is at most four links. Design an algorithm (pseudo-code) which identify, for any given sender, all the nodes able to receive adequate quality.

Problem 13.4 Concerns over Google’s use of personal information motivates an alternative route planner to Google Map, although not with a global ambition.

Explain how you can model the problem using graphs, and how you can algorithmically calculate the optimal route from A to B. Your answer must include a description of the data structure and pseudo-code for the algorithm.

Furthermore, discuss what we could mean by an optimal route, and how this is modelled in the graph. Discuss briefly a couple of alternative interpretations of «optimal».

13.2.3 Exercises

Problem 13.5 Consider the graph in Figure 1. Make a manual depth first search from node A, showing the steps, and the DFS tree you end up with.

Problem 13.6 Consider the adjacency map model. Draw a possible class diagram for an object-oriented implementation of the data structure and describe the purpose of each class.

Give pseude-code for the removeEdge(e) operation, making sure it runs in O(1) time.