木其工作室 QQ 928900200
COMP3712/8712 GE COMPUTER PROGRAMMING 3 ASSIGNMENT 2
Assignment 2: Shortest Paths in Graphs
Write a Java program that implements Dijkstra's algorithm to find shortest paths to all vertices in a
directed weighted graph from a given starting vertex.
As mentioned in the lectures, choosing an implementation for the data structure representing a
graph is highly dependent on the sparsity of the graph. For dense graphs, an adjacency matrix
representation is preferable, but for sparse graphs, an adjacency list representation may be more
efficient. You are asked to implement either the adjacency list or adjacency matrix representation
for graphs in your program. If you choose to extend you implementation from Lab03 then it will
need account for weighted edges.
Your program should (a) read in data defining a graph from a text file, (b) build an adjacency list OR
matrix representation of the weighted graph and (c) use the graph representation to find shortest
paths from a specified vertex in the graph to all other vertices, using Dijkstra’s algorithm*.
In addition, you should (d) provide documentation for your program describing how to run it, and
explaining how the code works. You should also justify your choice of data structures*, and details of
your code implementation, in terms of space and time efficiency.
*(e) Use both a standard List and Java’s builtin PriorityQueue for the storing the list of distances
from the given starting vertex to other vertices compare the performance (e.g. runtime, memory,
etc).
(f) Implement your own Priority Queue class using a Heap as described in lectures and tutorials.
Compare your implementation with the List and built-in PriorityQueue compare. Implementing your
own priority queue should allow you to make optimizations specific to the Dijkstra’s Algorithm (e.g.
not being generic) that the Java PriorityQueue must maintain to be widely usable.
Marking Guide
It is expected that all students attempt parts (a)-(f). All students should be able to complete parts
(a)-(d) and most should be able to complete part (e). Part (f) is potentially more challenging. The
table below gives an indication as to the distribution of marks to the parts of the assignment
described above.
Part Weight (100%) Weight (15%)
a 5 2
b 20 3
c 25 3
d 20 3
e 20 3
f 10 2
Total 100 15 COMP3712/8712 GE COMPUTER PROGRAMMING 3 ASSIGNMENT 2
Data Format: There are five example files (in Assignment02-data.zip) provided as example
input files. Feel free to test your program with your own files as well. The data format is as follows:
The first line contains the number of vertices.
Every line after that represents all edges going out from a particular vertex. The first number on each
line is the number of the vertex. After that, there are a number of pairs of integers. The first integer
is the index of a vertex connected to the first vertex in the line. The second integer is the weight of
the edge connecting those two vertices.
For example, if the text file content is:
4
1 2 18 3 12
2 1 22
3 2 16 4 14 4 1 31
then this means that there are 4 vertices, numbered 1 to 4. Vertex 1 has an edge to vertex 2, with
weight 18, and an edge to vertex 3 with weight 12. Vertex 2 has an edge back to vertex 1, but its
weight is 22 (because this is a directed graph, if there is an edge from A to B, it doesn’t mean that
there is an edge from B to A, or if there is, the weights don’t need to be the same).
Output: The graph in graphPosLittle.txt has size of 10 vertices. If coded correctly, a call to find
shortest paths from vertex 1 should produce the following output:
Shortest path to 1: 1: cost = 0
Shortest path to 2: 1 2: cost = 6
Shortest path to 3: 1 7 9 10 4 8 5 3: cost = 35
Shortest path to 4: 1 7 9 10 4: cost = 21
Shortest path to 5: 1 7 9 10 4 8 5: cost = 28
Shortest path to 6: 1 7 9 10 4 8 5 3 6: cost = 37
Shortest path to 7: 1 7: cost = 6
Shortest path to 8: 1 7 9 10 4 8: cost = 25
Shortest path to 9: 1 7 9: cost = 11
Shortest path to 10: 1 7 9 10: cost = 15
Submission of Assignment
Submission will be via FLO. A single zip file containing all source code and required documents. If
there are any special requirements for running the program these should be detailed somewhere,
preferably in separate document about running your program. Additional documents should be in
PDF format. If you have utilised additional data files for your assignment and they are too large to
upload to FLO then provide a link in your documentation.
相关推荐
数据结构Java版图3最短路径ppt课件.ppt
数据结构中最短路径的实现,用的是java语言,很简单很实用
Dijkstra-欧洲旅行 最短路径-Dijkstra-欧洲旅行 数据结构实验
最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形式包括: 确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。 [1] 确定终点的...
该文档讲述了java语言编写的实现最短路径的算法,简单易实现
java数据结构课程设计校园超市选址中,我们要用到弗洛伊德算法输出最短路径及最短路径长度,输出的路径用点--->点表示,本文件提供输出的代码。
数据结构—图及其应用(交通问题,实现最短路径、最短时间、最少费用查询),并且实现了简单的打印图。设计一个城市交通咨询模拟系统,利用该系统实现至少两种最优决策:最短路程到达、最省时到达等线路规划。
这个是我今年数据结构的课程设计。如果要课程设计报告书,请下载上面的
数据结构Java图最短路径PPT学习教案.pptx
数据结构课程实践:1. 问题描述: 以顶点表示校平面图中各景点,要有景点名称、代号、简介等信息;以边表示路径,存放路径长度等信息(路径长度可以估算,以米为单位)。 2. 要实现的功能: 1. 为来访客人提供图中...
自己写的一个关于有向图最短路径的程序,是在看完了谭浩强的《c++面向对象程序设计》后用面向对象方法写的。
主要实现查找任意两地点间最短路径并获得其长度,添加地点,删除地点,添加路线,删除路线操作 该系统带有模拟地图的加权无向图,直观的表现... 数据结构: 二维数组存储加权无向图 ArrayList存储地点,路径的相关信息
数据结构java类的dijkstra算法实现两城市最短路径
迪杰斯特拉算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。...Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。
Dijsktra算法实现 最短路径 Applet实现最短路径 完整数据结构,JAVA课程设计
本设计要求一个交通咨询系统,能让旅客咨询从任一个城市顶点到另一个城市顶点之间的最短路径、最低花费或最少时间等问题。对于不同的咨询要求,可输入城市间的路程、所需时间或所需费用。 一个简单的模型,采用邻接...
以下是关于Java数据结构和算法的一些介绍: Java作为一种流行的编程语言,在数据结构和算法的实现方面有着广泛的应用。数据结构指的是在计算机中组织和存储数据的方式,算法则是明确定义的解决特定问题的规则和步骤。...
具体任务 给出一张某公园的导游图,游客通过终端询问可知,从某一景点到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口。
数据结构图的方法包,包括图的邻接表和矩阵表示,图的遍历,添加删除点或边,最短路径,最小生成树。java语言
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...