Assignment Report for Algorithm and Advanced Data Structure

Completado Publicado Jul 23, 2014 Pagado a la entrega
Completado Pagado a la entrega

All Pairs Shortest Paths Problem (APSPP)

Consider a weighted complete graph G with vertex set G.V = {v0, v1, v2, …, vn-1}. The weight of the edge from vi and vj is denoted as G.w(i, j). It is assumed that the weights of the edges are non-negative. In other words, the weights satisfy the following constraints:

G.w(i, j) > 0 if i ≠ j

G.w(i, j) = 0 if i = j

The All Pairs Shortest Paths Problem (APSPP) is, given G, to find the distance network D which is a weighted complete graph such that

(i) D has the same vertex set as G.V. In other words, D.V=G.V= {v0, v1, v2, …, vn-1};

(ii) The weights of the edges in D represents the lengths of the shortest paths in G, In other words, D.w(i, j)=length of the shortest path from vi and vj

APSPP problem can be solved by the following approaches:

Approach A (Dijkstra’s algorithm): Repeatedly solving the Single Source Shortest Paths Problem (SSSPP) using Dijkstra’s algorithm which is a well known greedy algorithm.

Approach B (Floyd Algorithm): This approach solves APSPP using Dynamic Programming. It finds all the constrained shortest paths in the graph that only go via intermediate nodes {v0, v1, v2, …, vk}, for k=0, 1,2,.. n-1. When k=n-1, there is no more constraint. Thus all-pairs shortest paths problem is solved when k=n-1.

TASKS

1. Implement the following function,

Graph generateRandomGraph (int n)

that will generate a non-negative weighted complete graph with n vertices.

2. Implement the following functions that solve APSPP using Approach A and Approach B respectively. The headings of the function are as follows:

Graph repeatedDikstra (Graph G)

Graph floydAlgorithm (Graph G)

Input to the functions is a weighted complete graph G.

The output of the functions is the distance network D

3. Write a main program to test Approach A and Approach B.

o The program will generate a non-negative weighted complete graph G with the number of vertices specified interactively by the end user.

o The program will generate the distance network using repeatedDikstra(G), and measures the time taken to run the function.

o The program will generate the distance network using floydAlgorithm(G), and measures the time taken to run the function.

4. Write a report on your work. The report should cover the following issues: (i) Data structure design, especially the representation of complete graph; (ii) Pseudo Codes and activity diagrams for repeatedDikstra and floydAlgorithm; (iii) Test plan and test results for the correctness of repeatedDikstra and floydAlgorithm; (iv) Comparison of the execution time for Approach A and Approach B.

Programming language: recommend Java.

DEMONSTRATION:

The report must demonstrate the design, implementation and experiments of generateRandomGraph repeatedDikstra and floydAlgorithm.

Algoritmos Matemáticas

Nº del proyecto: #6224745

Sobre el proyecto

9 propuestas Proyecto remoto Activo Jul 26, 2014

Adjudicado a:

riskypathak

Hello. I am a algorithm specialist and can do this algorithm + report. Let me know if you are interested Thanks

$86 SGD en 2 días
(9 comentarios)
5.3

9 freelancers están ofertando un promedio de $118 por este trabajo

dobreiiita

Hello I am Algorithm and Java expert and can surely help you here with this project. I have a lot of experience in helping students with assignments and tutoring, So I am confident to handle this project. I am f Más

$100 SGD en 2 días
(93 comentarios)
5.7
IMRADIANTSUPREME

hello i am a phd in computer science and engineering. i can do this algorithm task perfectly. i can give you a sample solution(message me for that). plz provide detail information. thanks

$144 SGD en 3 días
(16 comentarios)
4.4
ghazalpasha

I'm very familiar with graph algorithms and can do this project in a day or so. Note that the bid is only for the coding part. If you also want the report done, I will need an extra day + extra $50.

$95 SGD en 1 día
(4 comentarios)
4.0
cimemi

Hello, I am a software engineer experienced in Java. The program will be completed within 2 days, and the report written in the third day, when I will also address any comments you may have.

$150 SGD en 3 días
(5 comentarios)
3.5
swarm22

Dear Sir, I have +5 year experiences in ms access database development. To Provide Quality, Modular , Result Oriented Work. Thanks & Regards HGDumaswala

$144 SGD en 1 día
(7 comentarios)
3.6
MSHARMA7

lemme see..................................................................................................................................................thnakx

$97 SGD en 1 día
(3 comentarios)
2.2
lizapolyudova

A proposal has not yet been provided

$100 SGD en 1 día
(0 comentarios)
0.0