Proposition P. (Shortest-paths optimality conditions) Let G be an edge-weighted digraph, with s a source vertex in G and distTo[] a vertex-indexed array of path lengths in G such that, for all v reachable from s, the value of distTo[v] is the length of some path from s to v with distTo[v] equal to infinity for all v not reachable from s. These values are the lengths of shortest paths if and only if they satisfy distTo[w] <= distTo[v] + e.weight() for each edge e from v to w (or, in other words, no edge is eligible).
This Proposition described a special state the cause-effect graph can reach -- among all the possible states of connecting the dots, there is one unique state of connecting them -- when reach that unique state, the graph reaches total relaxation. Given any point w in the graph, the chosen path from source to w is the shortest. You can not find an alternative path from source to w that is shorter. Given any point other than w, namely v, the path going through v either is on the chosen path, or on a longer path, but never on a shorter path than the chosen path.
"You might wonder how to reach that unique state for a given graph and the source. I'll tell you next, listen carefully, earthan."
Proposition Q. (Generic shortest-paths algorithm) Initialize distTo[s] to 0 and all other distTo[] values to infinity, and proceed as follows:
Relax any edge in G, continuing until no edge is eligible.
For all vertices w reachable form s, the value of distTo[w] after this computation is the length of a shortest path from s to w.
Remember, relax any edge as much as you can, until you reach that state -- total relaxation.
"Hey, wake up, earthan, you are almost there but took too long, let me tell you some techniques to reach total relaxation."
"If all the links are passive, you can start the relaxation from the source. Pay attention to your center of weight. Now, Start from there, relax all the links extending out from there. Let these links lead you to more points. Treat any of the newly discovered points as a source, extending out, find more points and relax more links. Until all the points are discovered and all the links are relaxed. At that point, you have reached total relaxation."
"Why? Please take a look at the prove of Dijkstra's algorithm."
"Wait, I almost forget, earthan's body don't have circle by default. Here is an even better technique for you."
"Forget about the center of the weight, Let's start the relaxation from the root, you feet, which bearing all the weights. Then moving upward, center of body, which bearing the weight of the trunk, moving upward, chest, which bearing the weight of shoulder, moving upward, head, upward, until the point bearing no weight. At that point, you have reached total relaxation."
"Why again? Please take a look at the prove of Proposition S."
Proposition S. By relaxing vertices in topological order, we can solve the single-source shortest-path problem for edge-weighted DAGs in time proportional to E+V.
"Try to reach total relaxation. Once you reach there, move. Your body changed into another weighted digraph, adjust to reach total relaxation for the new graph. Keep moving, but always relax. Wish the center of weight be close to you! Earthan, if you find the negative links and could not figure out, reach out to me, I will tell you something .."
Arbitrage.java
