Here is a problem: we are given a weighted DAG-that is, a directed acyclic graph with a weight on each edge. You can assume that all the weights are non-negative. One of the nodes is called start and another is called end. There are paths through the graph from start to end. Each path has a cost-this cost is the sum of the weights on edges that make up the path. The problem is to find a path of minimal cost from start to end.
Note that there might be more than one path of minimal cost. We only have to find one of them. And we are guaranteed that there is at least one path from start to end.
Before we go on, let me explain how the data will be input to the program you are going to write. There will be a file containing the specification of the graph. The name of the file will be dist.dat. That's it. You can't use any other file name. This is just to make things simple (even at the cost of being a bit user-unfriendly). Please don't try to change this.
A typical (but very small) dist.dat file might look like this:
(start p1 3)
(start p2 7)
(p1 p2 1)
(p2 end 11)
(p1 end 22)
Each line in the file looks like a Scheme list. Each line represents an edge in the graph. The first two elements in the list are the source and the target of the edge, in that order. The last element of the list-which is always a non-negative integer-is the weight of that edge.
you can use the following code to read in the graph:
;; read-file produces a list whose elements are the expressions in the file.
(define (read-file)
(let ((expr (read)))
(if (eof-object? expr)
'()
(cons expr (read-file)))))
;; Here we go: read in the file that defines the graph
(define data (with-input-from-file "dist.dat" read-file))
This will give you a variable named data that holds a list the elements of which are just the lines in the file dist.dat
The next thing you will need to do is to build a lookup table. This table should enable you to implement a lookup function (in fact, let's call it lookup) that takes the names of two nodes in the graph (like start and p2, for instance). If these two nodes are not the source and the target (in that order) of an edge, this function should evaluate to #f. Otherwise, it should evaluate to the cost of that edge.
Finally, we would like to print out, not only the minimal cost of getting from start to end, but also a path that has that minimal cost. (Remember that there might me more than one minimal path. That's OK; we only care about one, and it doesn't matter which one.)
To do this, you will also need to memoize a shortest path from each node to end. In principle, this is not at all hard to do, but you will need to be careful.