All Source shortest path using fibonacci binomial &simple

• Project ID:

  460020

• Project Type:

  Fixed

• Budget:

  $30-$250 USD
  

Project Description:

1. Problem

You are required to implement Dijkstra's Single Source Shortest Path, say SSP, algorithm for directed graphs using a simple data structure, say simple scheme, Fibonacci heaps, say F-heap scheme, and Binomial heaps, say B-heap scheme, and measure the relative performance of the three implementations. Although Dijkstra’s algorithm was developed to find a shortest path from a single source vertex to each of the remaining vertices (single-soure all-destinations), we shall use it here for the all-pairs shortest paths problem by running the algorithm once with each vertex as source.

The simple scheme should not use complex data structures, e.g., a min heap or a Fibonacci heap, but use array(s) and should run in O(n2) time. The F-heap scheme computes the dist[ ] array by making use of Fibonacci heaps. The B-heap scheme computes the dist[ ] array by making use of Binomial heaps.
2. Input Requirements

1. Running modes:

The name of your compiled program should be ssp(c, c++), ssp.java for Java. Your program must support all of the following modes.

(1) random mode: run with graphs generated by random number generator.

$ ssp -r

(2) user input mode: run with the graph input from a user

(i) user input mode using simple scheme

$ ssp -is // read input interactively
$ ssp -is file-name // read redirected input from

a file file-name

(ii) user input mode using F-heap scheme

$ ssp -if // read input interactively
$ ssp -if file-name // read redirected input from

a file file-name

(iIi) user input mode using B-heap scheme

$ ssp -ib // read input interactively
$ ssp -ib file-name // read redirected input from

a file file-name

While in the random mode, there is NO input from user. In the user input mode, your program has to support both interactive and redirected input from a file "file-name" which contains a directed graph representation.

Note: Your program should provide exactly same format specified above.

2. Input format in the user input mode:

Note: Please do not use other input format for the graph representation.

Your program needs to determine how many nodes are in the graph. You can easily do that by examining data.

In the user input mode, your program must conform the

V1 V2 C1 // the edge (V1, V2) with cost C1

V2 V3 C3 // the edge (V2, V3) with cost C3

...

* // the end of input



Assume that vertices are labeled from 0 to n-1.

An example input is shown below:


0 1 5

1 2 8

*


The graph consists of three vertices {0, 1, 2} and two directed edges <0,1> and <1,2> with costs 5 and 8 respectively.

　


following input format:



　

　The graph input for testing may not be a connected graph. For unconnected graph input, your program should compute dist[ ] values to reachable nodes.




3. Output Requirements

In the user input mode, your program should display the dist[ ] array just after finding all the shortest paths. It is used for testing purposes. An example output of user input mode is below:

　

Distance Matrix:

The above results indicate that "0" is the source node and the distance from the source to node "1" is "3" and so on.

Note: We will assume a graph of n vertices labeled from 0 to n-1. If you use different labeling in your implementation, you need to do the conversion before displaying the dist[] array. Your program should not display any other information such as time taken in the user input mode.

An example output of random mode is below:

Number of vertices Density Simple scheme(msec) F-heap scheme (msec) B-heap scheme(msec)

100 10% ? ? ?

100 20% ? ? ?

. . . . .

. . . . .

300 50% ? ? ?

. . . . .

. . . . .

500 100% ? ? ?

　

You program should display the execution time and don't display the dist[] array in the random mode.

Skills required:

C Programming, Java