CSC 372
Laboratory:  Dijkstra's Algorithm

Uses

• lab5.cpp
• graph1.txt
• graph2.txt
• graph3.txt
• (perhaps stack.h and stack.cpp to assist in printing out the shortest paths )

Background

• The file lab5.cpp contains the skeleton for a shortest path algorithm implementation of a one-source shortest paths to every node algorithm. Your program should code the Dijkstra’s algorithm on page 278. Since Dijkstra’s algorithm does not work well with negative weights, these values are changed to their absolute values.

Requirements:

• Implement Dijkstra’s algorithm and print out the shortest paths from node 0 to all others. All graphs are assumed to be weighted. The output of the program should be a listing of all paths from 0 to each other node. Use the predecessor array in the algorithm to provide the needed paths from node 0. It is also best to set the predecessor array at 0 to be –1.
• Hand in your program and all associated files on a 3.5" diskette

© Computer Science Department NSU.
Permission granted for non-commercial use only.