Implementations of several different generalized shortest path algorithms. These algorithms are a combination of geometric search and dynamic-programming implementations. We show that different Bellman-Ford-Moore-like implementations have asymptotically different running times and these running times differ from those for ordinary shortest path problems.
The program solves the network flow optimization problems of minimum-cost and no-cost multicommodity flows. The problems involve allocating shared resources among flows between different locations. Given a graph, an arc capacity function, a set of commodities (a source node, a destination node, and a demand), and an arc cost function, determine the cheapest way to route each commodity's flow so the total flow (of all the commodities) on any arc is at most its capacity.
Given two character sequences, e.g., DNA bases, introduce gaps into the sequences so as many characters match as possible. Sequence alignment is used frequently to identify and match gene sequences. This dynamic programming implementation has been used in Stanford University's MIS 214/CS 274 course since 1995.
Added color graphics to the ParaScope Editor research tool, an interactive tool to find and exploit parallelism in sequential Fortran programs.