Highest Paid Toll

Problem Name: Highest Paid Toll
UVa ID: 12047
LightOJ ID: 1379 (under the name “Toll Management”)
Keywords: graph theory, single source shortest path, dijkstra

Let me share with you a little story from my childhood. When I was a kid, one of the first books I really enjoyed —and one which remains a cherished piece in my bookshelf to this day— was a mathematics book they made me read in elementary school. It wasn’t your average elementary math book, however. It was written by a professor from a local University, and the book had a very friendly and humorous approach to the concepts it presented (without being patronising), and at the same time it was rich in content and rigorous. It also contained a good deal of material not directly related to mathematics, like philosophy, literature, humanities, puzzles… well, you get the idea. In short, to a small curious kid with a yearning for understanding more about this world, this book was (and still is) simply fantastic. Anyway, one of the lessons I learned from it comes at the beginning of the section devoted to puzzles, where some general ideas for problem–solving are discussed. That chapter contains a list of tips to approach a new problem, and among them is the question “Can you make a drawing?”, and then in a smaller font (the “informal” voice inside the book) there was the complementary statement: “you can always make a drawing, do it!”

The point of this long–winded introduction is simply this: you can indeed always do a drawing… give it a try. This is not a novel idea by any means, of course, it’s just one that was strongly impressed upon my memory from those days, and which I apply constantly ever since. Granted, most of the time I try to do the “drawing” in my mind, whenever I’m able to fit the entire problem in my head, but if I can’t do that I quickly resort to a pen and a sheet of paper and start doodling around. This problem is just an exceptionally good example of an instance where something that was initially confusing, all of a sudden revealed its simplicity and elegance once I just started drawing things. This will all become clear in a moment —at least I hope so, if not, try doing a drawing about this post, a meta–drawing if you will :).

Here’s the summary of the problem. You receive a directed, weighted graph. Two nodes are defined as source (\(s\)) and sink (\(t\)), and you also receive a number \(p\) which denotes a “cost limit”. You have to find the heaviest edge inside any valid path between the source and the sink; a path is valid if its total cost doesn’t exceed \(p\).

Clearly, this is not your standard single–source shortest path problem. However, there is a nice solution based on the SSSP algorithm. As usual, let’s begin with an arbitrary example that helps us tame this puzzle. Consider the following graph:

Try to find the answer for this example. That is, identify all paths from 1 to 9 with a total cost less than or equal to 100, and among those paths, determine the edge with the largest cost. Given that the answer becomes obvious from the following graphs, I might as well tell you now that it is the edge \(2 \rightarrow 4\) with a cost of 53.

What I will ask you now is, forget about this specific example. Generalise things in your mind. The next graph presented below will look familiar, but keep in mind that this is just a simplified representation of the general problem. You can be fairly certain that the real test cases for this problem from the judge will contain all kinds of complicated graphs, with many more nodes, edges, multiple edges between the same pair of nodes, unconnected components, etc. But this representation is just an aid that helps us wrap our minds around the core of this problem.

That being said, imagine now an arbitrary graph for which there is a valid answer. That means that there is one edge that belongs to a valid path from the source to the sink, and that edge has the highest cost possible among all the alternatives. Let’s paint that edge with a distinctive color, like red. That graph might look something like this:

Okay, now… if this edge, let’s call it \(u \rightarrow v\), really exists and is a valid answer, then it implies a number of things:

• There has to be a path \(s \Rightarrow u\).
• Similarly, there exists a path \(v \Rightarrow t\).
• Perhaps the most significant implication of all, the sum of the costs of \(s \Rightarrow u\), \(u \rightarrow v\) and \(v \Rightarrow t\) has to be less than or equal to \(p\).

Let’s put all this information in a new graph that depicts the relevant nodes and paths:

When you think about the green paths, does anything come to mind? For me this was the moment when something “clicked” in my head. I started having no idea how to solve the problem, but when I drew something like this the strategy made itself evident; but let’s keep going.

I hope you can see where this is going. If there is an edge \(u \rightarrow v\) that is our answer, then it would be useful to know the shortest possible paths \(s \Rightarrow u\) and \(v \Rightarrow t\), wouldn’t you agree?

With this in mind, let’s formulate the following algorithm to solve the general problem:

• Start with two graphs: the original graph (let’s call it \(G\)) and a reverse graph (let’s call it \(R\)).
• Find all shortest paths in \(G\) from \(s\).
• Find all shortest paths in \(R\) from \(t\).
• Let \(A\) be the answer. Initially, \(A = -1\).
• For each edge \(u \rightarrow v\) in \(G\) with cost \(w\):
  • Determine the total cost \(C\) of \(w\) plus the shortest paths \(s \Rightarrow u\) in \(G\) and \(t \Rightarrow v\) in \(R\).
  • If \(C \leq p\) and \(w > A\), then set \(A = w\).

That’s it. Running an algorithm like Dijkstra’s two times and then traversing over all the edges is quite enough to reach the solution.

Needless to say, the best part for me was having an Eureka moment right after doing one of my primitive drawings in a piece of paper. This is what intrigues me, though: the drawing I did was not particularly “interesting”; it was just a rather generic graph. Yet somehow, seeing the nodes and edges drawn in a piece of paper, and assigning colors to some edges made all the difference. It’s like it made all the processes inside my brain go faster… Maybe you understand what I’m talking about. If you don’t, can I suggest that you try doing more drawings in the future? Even if they are so trivial that it might seem silly to spend the time drawing something so elementary. The results might surprise you.