All Pairs Shortest Paths Problem (using java to find)

已完成 已发布的 Aug 17, 2014 货到付款
已完成 货到付款

ASSIGNMENT QUESTION (100%)

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.

Java

项目ID: #6333636

关于项目

1个方案 远程项目 活跃的Aug 17, 2014

授予:

mingzixian523

Hello, sir. I have enough experience for your task. I'm ready to start now. If you award me, I'll send you result after 3 hours. Thanks. Regards,

$147 SGD 在0天内
(6条评论)
4.1