Saint Mary’s University

Department of Mathematics and Computing Science

CSC 342.2: Data Structures and Software Engineering II

Winter 1999-2000

Assignment #5

Instructor: Dr. Pawan Lingras

Due Date: March 23, 2000

Let us assume that we have a building represented using a graph. Each room in the buliding is represented by a vertex. If there is a direct hallway from room v1 to room v2 there is an edge (v1, v2) in the graph. Each room has a key (five character long string) to enter the room. Each edge has a weight that corresponds to the length of the hallway.

Write a program that allows a user to find the shortest path from a room origin to another room destination. The person will have a set of five keys.