代做Draft Copy、代写C/C++编程、代写C/C++语言、代做algorithm

日期：2018-12-17 09:46

Programming Assignment 4 --- Fall 2018 (Draft Copy)

Purpose of the Project

The primary goal of this exercise is to develop skills to work with graphs. A secondary goal is to apply Dijkstra’s algorithm to compute the shortest path for problem represented as a graph.

Description

You will be given data in the form of nodes and edges. The first line of the data file is the number of nodes. Nodes are identified by integers and will go from 0 to the number of nodes – 1. Next is the start node. Following the start node is a list of edges and weights. Each line will contain a source node, destination node, and a weight (real number). The end of data is marked by the end of file.

Details

The input data may represent cities. You are to use the Dijkstra’s algorithm to determine the shortest path for graphs that are described by the format defined in this exercise. Your solution must work for graphs that have at most 100 nodes. You are to use the Priority Queue you have designed for your last Programming Assignment, Project 3. You must add a header file mypq.h to your solution. This file will contain the C/C++ function declarations and any macro definitions that are associated with your priority queue implementation and will be shared by other source files, used for your solution, that require a priority queue. Your solution will have the #include “mypq.h” statement as part of the header declaration of the components that manipulate the priority queue.

Input Data Format Example

The data in your testing files must follow the format here defined. The example that follows illustrate the format to be used.

6

1

0  1  12.0

0  2  8.5

0  3  5.5

2  4  4.0

4  5  10.0

3  5  15.0

Output Format

Your solution must report the shortest-length path for all nodes starting from the defined origin as determined by the associated input file. You are to place your solution in a text file. The format to be followed is described below for a graph with 5 vertices <S, T, X, Y, Z>, and S as the start node. Note: Both the path and the integers used for the example below are just for the description of the format to be used.

The shortest-length path is:

S = 0; path = < >

T = 4; path = < S, Y, T>

X = 9; path = <S, Y>

Y = 5; path = <S, Y, Z>

Z = 7; path = <S, Y, T, X>

How to Submit your Work

Your solutions must be submitted to the address provided by your co-instructor.

Your files for the Project4 must include the source code for all modules used for the exercise as well as an executable file to allow your solution to be tested. You must include all your source files in a Compressed (zipped) folder (.zip). Your (.zip) folder as well as the subject of your message must follow the format:  Project 4 Your Name. Marks will be deducted if you do not follow this requirement.

Due Date

The project is due on Friday, December 21st, 2018.

Expectation

Your program should be layered, modularized and well commented. The following is a tentative marking scheme and what is expected to be submitted for this assignment:

1.External Documentation including [5-10 pages]

a.Title page

b.A table of contents

c.[10%] System documentation

i.A high-level data flow diagram for the system

ii.A list of routines and their brief descriptions

iii.Implementation details

d.[5%] Test documentation

i.How you tested your program

ii.Testing outputs

e.[5%] User documentation

i.Where is your source

ii.How to run your program

iii.Describe parameter (if any)

2.Source Code

a.[75%] Correctness

b.[ 5% ] Programming style

i.Layering

ii.Readability

iii.Comments

iv.Efficiency

编程作业4 --- 2018年秋季（草稿副本）

项目目的

本练习的主要目标是培养使用图表的技能。第二个目标是应用Dijkstra算法来计算以图表形式表示的问题的最短路径。

描述

您将以节点和边的形式获得数据。数据文件的第一行是节点数。节点由整数标识，并将从0到节点数 -  1.接下来是起始节点。在开始节点之后是边和权重的列表。每行将包含源节点，目标节点和权重（实数）。数据的结尾由文件末尾标记。

细节

输入数据可以代表城市。您将使用Dijkstra算法来确定以本练习中定义的格式描述的图形的最短路径。您的解决方案必须适用于最多包含100个节点的图形。您将使用为上次编程分配，项目3设计的优先级队列。您必须将头文件mypq.h添加到您的解决方案中。此文件将包含C / C ++函数声明以及与优先级队列实现关联的任何宏定义，并将由需要优先级队列的其他源文件（用于解决方案）共享。您的解决方案将#include“mypq.h”语句作为操作优先级队列的组件的头部声明的一部分。

输入数据格式示例

测试文件中的数据必须遵循此处定义的格式。下面的示例说明了要使用的格式。

6

1

0 1 12.0

0 2 8.5

0 3 5.5

2 4 4.0

4 5 10.0

3 5 15.0

输出格式

您的解决方案必须报告从相关输入文件确定的定义原点开始的所有节点的最短路径。您将解决方案放在文本文件中。对于具有5个顶点<S，T，X，Y，Z>和S作为起始节点的图形，下面描述要遵循的格式。注意：以下示例中使用的路径和整数仅用于描述要使用的格式。

最短路径是：

S = 0; path = <>

T = 4; path = <S，Y，T>

X = 9; path = <S，Y>

Y = 5; path = <S，Y，Z>

Z = 7; path = <S，Y，T，X>

如何提交你的作品

您的解决方案必须提交给您的联合指导员提供的地址。

Project4的文件必须包含用于练习的所有模块的源代码以及允许测试解决方案的可执行文件。您必须将所有源文件包含在压缩（压缩）文件夹（.zip）中。您的（.zip）文件夹以及邮件主题必须遵循以下格式：项目4您的姓名。如果您不遵守此要求，将扣除标记。

截止日期

该项目将于2018年12月21日星期五举行。

期望

您的程序应该是分层的，模块化的和良好的评论。以下是暂定标记方案，预计将为此项目提交的内容：

1.外部文件，包括[5-10页]

一个。封面

湾目录

C。 [10％]系统文档

一世。系统的高级数据流图

II。例程列表及其简要说明

III。实施细节

d。 [5％]测试文档

一世。你是如何测试你的程序的

II。测试输出

即[5％]用户文档

一世。你的来源在哪里？

II。如何运行你的程序

III。描述参数（如果有的话）

2.源代码

一个。 [75％]正确

湾[5％]编程风格

一世。分层

II。可读性

III。评论

IV。效率