Shortest path and Max flow project

Cancelado Publicado Nov 8, 2007 Pagado a la entrega
Cancelado Pagado a la entrega

**Description:

** The goal of this project is to compare the running times of various algorithms in practice to their worst-case running times.

Write program(s) Java/MATLAB that computes the shortest paths from node 1 to all other nodes in the network and the maximum flow from node 1 to all other nodes. Your program should take as command line input either 4 or 1 additional arguments. The four arguments should be the values for n, m, C, and U. In this case, the program should create a random network topology by connecting nodes with links. The head and tail of all the m links should be chosen uniformly between 1 and n. Similarly, the link costs should be uniformly chosen in the range [-C, C] and the capacity upper bounds in the range [0, U]. Make sure that your project deals with the case if the network is disconnected. For the case of a single argument, the topology of the network should be read from the filename specified as the argument.

Check if the network has cycles or negative link costs. In the absence of cycles, **apply the acyclic networks algorithm** **to find shortest paths from the source to all the other nodes**. In the absence of negative link costs, **apply the Dijkstra’s algorithm to find the shortest paths** from source to all the other nodes. In the presence of negative cycle(s), list the arcs that form the cycle(s). If the network has negative link costs but no negative cycles, apply **the modified label correcting algorithm to find the shortest paths.**

Also, implement the algorithms for solving the **maximum flow problem namely the shortest augmenting path, capacity scaling and the FIFO pre-flow push algorithm.**

## Deliverables

1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done.

2) Deliverables must be in ready-to-run condition, as follows (depending on the nature of the deliverables):

a) For web sites or other server-side deliverables intended to only ever exist in one place in the Buyer's environment--Deliverables must be installed by the Seller in ready-to-run condition in the Buyer's environment.

b) For all others including desktop software or software the buyer intends to distribute: A software installation package that will install the software in ready-to-run condition on the platform(s) specified in this bid request.

3) All deliverables will be considered "work made for hire" under U.S. Copyright law. Buyer will receive exclusive and complete copyrights to all work purchased. (No GPL, GNU, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site per the coder's Seller Legal Agreement).

4)Consider node 1 as the source for the shortest paths and the maximum flow algorithms. The destination for the maximum flow algorithms should be node n. Execute the program multiple times with various values of n, m, C and U and measure the running time of your implementation. Your goal is to compare the running times of these algorithms in practice to their worst-case running times. For each set of (n, m, C, U) values, generate at least five different (random) networks, and record the running time taken by each algorithm. To ensure uniformity, run the different algorithms on the same instances (i.e., do not generate new networks for each algorithm).

5)Make sure that the code is commented properly. The structure of the code should make the verification easy.

6)I also need a complete report along with a flow chart of the whole program as well as the flow charts of each algorithm individually. Make a complete report and compare running times of each algorithm.

7)I would prefer if code is written in Matlab.

## Platform

It should be able to run on both Windows XP and Unix

Ingeniería Linux Microsoft MySQL PHP Arquitectura de software Verificación de software UNIX Windows Desktop

Nº del proyecto: #3455869

Sobre el proyecto

Proyecto remoto Activo Nov 8, 2007