CSCI 260 Fall 2026: Lab 5 : Graphs: Dijkstra's Algorithm




 65% correctness, 20% design decisions, 15% style.
Style includes use of white space, comments, variable naming, among other factors.
Design decisions include information hiding, modularization, efficiency considerations, data organization, proper use of vectors, among other factors.

Graph Algorithms This lab builds on your graph data structure from Lab3 and Lab4. You will implement Dijkstra's Shortest Paths algorithm.



Getting started

  1. Use git to create the Lab5 repository.
  2. Copy over your Lab4 files for graph.cpp and graph.h. You can do this by changing directory to your csci260 directory, then executing the following commands:
    cp Lab4/*.cpp Lab5/.
    cp Lab4/*.h Lab5/.
    cp Lab4/makefile Lab5/.
    cp Lab4/gen Lab5/.
    You will need to update the testapp.cpp file to reflect a menu option ``S" for the user to select for finding Shortest Paths.


The Input
Your program will read in graph data in the following form: 
5
0 1 24
1 4 3 
1 2 16
3 2 14
4 2 6 
4 2 9 
5 5 5
This file is interpreted as follows:
5 vertices, (implicitly named 0, 1, 2, 3, 4)
vertex 0 has an edge to vertex 1 with weight 24 (implicitly, since the graph is undirected, vertex 1 has an edge to vertex 0 with weight 24 as well.) vertex 1 has an edge to vertex 4 with weight 3; etc. That is, after reading in the number of vertices, integers are to be taken in triplets, where the first and second integers are the vertex numbers, and the third is the weight of the edge.

For ease of input, the file contains only integers.

The signal that the end of the file has been reached is when the first number in the triplet is any number ≥ n. Any triplets where the second integer is ≥ n should simply be ignored. If the file ends after reading two valid vertex numbers (i.e., no edge weight is given) the edge should be ignored and the graph input will be deemed completed.



The most important thing is correctness; second is comprehensibility, which includes good design, and third is is software engineering principles like polymorphism.
Your graph code must be your own. Do not use AI for code generation.


Your Task for this lab:
You have been provided with code structure to read in a weighted graph and run graph algorithms on the graph. You have updated it for your Lab4. You have also been provided with a testapp program and a header file.
Debug-print the graph is provided for you. For example, the output for a graph could be: 
0:    1 (24),
1:    0 (24), 4 (3), 2 (16),
2:    1 (16), 3 (14), 4 (9),
3:    2 (14),
4:    1 (3), 2 (9),


Your main tasks are as follows:

  1. Update the testapp program to handle the ``S" (for Shortest Paths) command option.
  2. Add to the graph.cpp code the function with the following prototype, and update your header files with the prototypes in it.
    void shortestPaths(int s)
  3. As discussed in class, to implement Dijkstra's shortest paths algorithm, you will need to declare an nxn array; you should call it distancePath. You will need to report the shortest path as a sequence of vertices, and the last edge in the path.
    Shortest paths from vertex 5:
    1: 5 <13> 6 <2> 3 <18> 1. Total path distance: 33
    2: 5 <14> 2. Total path distance: 14
    3: No path
    etc.
     For this, it would be good to declare a struct, call it pathEdge, associated with each vertex, that gives the information you need to keep for that vertex in order to reconstruct the path from s to the vertex. The struct pathEdge might have three parts, an integer for previous vertex in the path; an integer for the edge weight of the edge between the previous vertex and the current one; and the weight of the total path from s that leads to thhe current vertex. therefore you will also need It can be declared within the shortestPaths subroutine.
  4. Implement shortestPaths, with the result being that all shortest paths from s to every other vertex in its connected component are known. Your program should just compute the shortest path for the vertices in the connected component containing the input vertex s.
  5. When you print out the paths, they should start at s and proceed to the vertex in question. However, the path is reconstructed in the reverse direction. You may want to declare a stack<pathEdge>. Stacks are part of the Standard Template library.



Duplicate edges, self-loops, and disconnected graphs
The input graphs may have any of the above. Your code should handle these situations gracefully. Your implementation from Lab3 should have dealt with duplicate edges: the 2nd edge overwrites the first. However, your program must be able to encounter self-loops.
For disconnected graphs, you should print out paths only for the vertices reachable from the input vertex. Your program should detect when no path was found from s to a particular vertex, and you should print out "No path" as the result, as noted above.

Test your code thoroughly.


Everything but the data files and the makefile should bear your complete name and student number. Code should be well-documented and well designed. Files are to be submitted via git.


Here is the perl file for generating a graph file at random.

#!/usr/bin/perl
use strict;
use warnings;

my $n;
my $m;
my $w;

# you may want to hash-out/ comment out the printing, or just remove
# the prompts from the files you generate, if you use >> to gen the
# data into a file
print "How many vertices: ";
$n = ;

print "How many edges: ";
$m = ;

print "max edge weight: ";
$w = ;



print $n;

my $count = 0;
while ($count < $m)
{
$count= $count + 1;
my $u = int(rand($n));
my $v = int(rand($n));
my $weight = int(rand($w));
print $u, " ", $v, " ", $weight,"\n";
}
print $n," ",$n," ",$w;

#end of gen
22
0 1 1
0 12 1
1 18 1
1 6 1
6 9 1
9 4 1
9 7 1
4 113 1
7 11 1
11 17 1
3 2 1
3 5 1
2 8 1
5 14 1
14 10 1
8 10 1
10 15 1
15 16 1
19 20 1
22 22 1