联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-21:00
  • 微信:codinghelp

您当前位置:首页 >> C/C++编程C/C++编程

日期:2022-05-16 08:22

159.201 Algorithms & Data Structures

S1 2022

Assignment 6

Write a C++ program to implement Dijkstra's algorithm that can find the minimum costs from node A to all other

nodes. A generic graph with an arbitrary number of nodes is written into a text file, and the program should be

able to read it and insert nodes and costs into a class called Graph (see week 6 slides).

The txt files contain nodes and direct costs from a node to some other node. An example with 3 nodes is:

Node B

Node C

Node A

A B 10

A C 5

B A 3

B C 2

C A 4

C B 1

The text file above would represent the following graph:

After running Dijkstra's algorithm, the output should be the minimum cost from node A to every other node. An

example of the format for the output is shown below:

From A to B:6

From A to C:5

NOTE: the names for the nodes is out of order (see the content above). Therefore, you need to use a function to

discover the index of the node when using the adjacency list. The final answer should be given in alphabetical

order.

There are 5 sample txt files called graph*.txt available on Stream. The number of vertices in those graphs vary

from 3 to 20. It is important that the number of nodes and the number of paths can be allocated dynamically.

Therefore, your Graph class needs to use an adjacency list. There are a number of options to achieve that using

vectors and/or linked-lists. We have seen an example using vectors for the vertices, with elements that contain a

pointer to a linked-list, which then contains the costs to reach a certain vertex. For more details on how to

implement this assignment, refer to the material of the tutorials.

Use our virtual machine to mark your submissions (host name vm000296). The input/output requirements are

essential, please follow them carefully to avoid losing marks. Spaces matter and text is case sensitive.

After you are satisfied with the performance of your code as tested in the virtual machine, submit a one source

file code on Stream by Friday 20 of May 2022. Your name and ID number must appear on top of the file as

comments. If you are working in a group, then all names and IDs must appear on top of the file as comments, but

you still need to submit individually in both the virtual machine and Stream.


相关文章

版权所有:编程辅导网 2021 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp