Find Jobs
Hire Freelancers

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. -- 2

$100 USD

已完成
已发布将近 10 年前

$100 USD

货到付款
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: must demonstrate the design, implementation and experiments of generateRandomGraph repeatedDikstra and floydAlgorithm. SUBMISSION o The soft copy of the report in both WORD and PDF format; o The source codes and executables for the program; o The raw data from the experiments;
项目 ID: 6097587

关于此项目

3提案
远程项目
活跃10 年前

想赚点钱吗?

在Freelancer上竞价的好处

设定您的预算和时间范围
为您的工作获得报酬
简要概述您的提案
免费注册和竞标工作
颁发给:
用户头像
Hi Brother I am Expert in algorithm and Java I can do this Please check my past project reviews Thank You :)
$105 USD 在3天之内
5.0 (14条评论)
4.2
4.2
3威客以平均价$109 USD来参与此工作竞价
用户头像
hi...............message me ..................i have previously implemented these algorithms............i get it done for you in time according to your specifications...........waiting for your response to start................Thank you...........Regards
$100 USD 在1天之内
4.8 (8条评论)
3.7
3.7
用户头像
A proposal has not yet been provided
$111 USD 在3天之内
5.0 (3条评论)
1.3
1.3
用户头像
Hi, this is a basic task so i think you need a good algorithm and I have 2+ years of experience in Mobile Development with strong programming knowledge in Android ,java Technology. I will be providing it in future .Best regarding,thanks!
$111 USD 在3天之内
5.0 (2条评论)
1.2
1.2
用户头像
hi, sir, i will glad to work with you, i have more then 2 years of experience of java technology, if you assign this project today then i will done and submitted this project at tomorrow same time.
$100 USD 在1天之内
0.0 (0条评论)
0.0
0.0

关于客户

SINGAPORE的国旗
Singapore
4.6
8
付款方式已验证
会员自6月 21, 2014起

客户认证

谢谢!我们已通过电子邮件向您发送了索取免费积分的链接。
发送电子邮件时出现问题。请再试一次。
已注册用户 发布工作总数
Freelancer ® is a registered Trademark of Freelancer Technology Pty Limited (ACN 142 189 759)
Copyright © 2024 Freelancer Technology Pty Limited (ACN 142 189 759)
加载预览
授予地理位置权限。
您的登录会话已过期而且您已经登出,请再次登录。