ECE 36800 Traffic

ECE 36800 Assignment #8 

 Original Due: 1:00 PM, Tuesday, November 19 

 Extended: 1:00 PM, Tuesday, November 26 

Goal 

Consider the following scenario: you want to find an optimal route for your commute to work 

while considering factors like traffic, which may change over time. We can model this as a graph 

where each edge has a list of weights, such that each element of the list reflects the weight of that 

edge after a certain number of steps. For instance, consider the path given by 0 → 1 → 2 → 0 on 

the graph below: 

The weight of the 0 → 1 edge is initially 1. After taking the first step, the weight of the 1 → 

2 edge is 5, and after the second step, the weight of the 2 → 0 edge is 9, so the total weight of the 

path is 1 + 5 + 9 = 15. 

For simplicity, we only consider graphs where the lists of weights for each edge all have the same 

length, called the period. In general, if an edge u → v shows up at position i in the path and has a 

weight list of (x1, . . . , xn), it contributes xi mod n to the weight of that path. The goal of this 

assignment is to write a program which, given a graph like the one above, and a pair of start/end 

vertices, outputs a path from start to end with minimum weight. 

Input/Output 

As before, your program should take as a command-line argument the name of a text file 

describing a graph, and then respond to queries on standard input. For each query, you should 

print to standard output the shortest path as a space-separated list of vertices. 

The format of the text file is as follows: 

• The first line will look like V N , where V is the number of vertices in the graph, and 

N is the period of the edge weights. 

• Following that, there will be one line per edge, in the format 

vs vt w1 . . . wN 

where vs is an integer representing the source vertex of the edge, vt is an integer 

representing the target vertex of the edge, and each of w1 through wN are integers 

representing the list of weights for that edge. 

Each query will be given by a space-separated pair of integers, representing the indices of the start 

and end vertices, respectively. 

© 2024, Jongwook Kim. All rights reserved. 

Example 

Consider the following graph.txt file: 

This represents the graph: 

A sample run of the program is shown below: 

$ ./a8 graph.txt 

where 0 3 is the query input on stdin and 0 1 2 3 is the shortest path. Explanation: the shortest 

path from 0 to 3 is 0 → 1 → 2 → 3 with a total weight of 5 + 2 + 4 = 11, since the 

other path 0 → 2 → 3 has a total weight of 3 + 15 = 18. 

There will be multiple queries for each graph, but you may assume that all queries with the same 

start vertex will be given consecutively. 

Grading 

Similar to the previous programming assignment, your submission must be both correct and 

efficient (and not have any memory leaks/errors, as usual) to receive full points. The graphs will 

range in size from 10 vertices to roughly 1k vertices, and each graph will have approximately 10 

queries. For each test case, your program must produce an output within the time limit to receive 

credit. You should put a comment at the start of each method describing its functionality. 

Submission 

Submit any source/header files with your implementation, as well as a Makefile that builds 

a target called a8, to Gradescope. DO NOT include executables in your submission. DO NOT 

put your files inside a folder. Note that to receive points, your submission must work on 

eceprog.