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.
4,15
請加QQ：99515681 郵箱：
[email protected] WX：codinghelp
