Java代写：COMP206GraphTraversalandDijkstra'sAlgorithm

代写Dijkstra算法，对地图上的任意两点，求最短路径。

Requirement

In this project you will use the Graph ADT and Dijkstra’s algorithm to compute
the length of the shortest path (number of nodes visited), and for extra
credit the path with the fewest turns. The input graphs are actual street map
of Manhattan NY and Manhattan Kansas

Objectives

The goal of this programming project is for you to master (or at least get
practice on) the following tasks:

• Establishing a Graph ADT from a real life application
• Using Dijkstra’s algorithm to find length of a path.
• Inputting user origination and destination information
• working with existing code

Helpful code

The main class that will call methods the Graph ADT in chapter 10 which are
also provided attached to the assignment. This java project ProgProject4
provides and application that creates a graph using the books graph ADT
classes. There is also a package that contains a class to execute Dijkstra’s
algorithm.

Project Steps

1. Create a graph based upon the given street map. Each expected vertex in your graph is represented by a blue dot. The blue dots represent a traffic intersection. Your vertex should be an instance of an Intersection Class, not a String as used in most class examples. Your program should read an input file containing all information about the intersection including all streets that meet at that intersection.
2. Traverse through the graph and find the length, or the number of nodes , of the shortest paths for the origination to destination path.
3. For 5 points extra credit, find the path with the shortest number of turns. A turn is defined as a path of 3 vertices where the edge street names are not the same.
   Hint - for fewest number of turns, store the name of the street of the edge. A
   turn is when a vertex on the path is reached by 2 edges with different names.

Notes

When inputting an intersection, always assume street names are sorted, and
only the street name (not ave or road) is provided.
Ignore One Way arrows on maps
Expected Results:
Map 1: Manhattan Kansas
Input:
Origination: Hudson,Kimball Destination: Claflin,Denison
Output:
Minimum Path Length: 6 Minimum Turns: 1
Input:
Origination: College Destination: Claflin,NManhattan
Output:
Minimum Path Length: 4 Minimum Turns: 1
Map 2: Manhattan New York
Input:
Origination: Canal, Spring Destination: Spring, Thomson
Output:
Minimum Path Length: 5 Minimum Turns: 1

Running the program

Since you will be using the ProgProject4 class provided, running your program
should be produce a series of input prompts for the origination and
destination locations.

Grading Criteria

1. Program asks for proper input and builds the graph
2. Program asks for proper input and recognizes the start and end vertex
3. Results for the length (Number of nodes) in shortest path is correct
4. Results for least number of turns in a path is correct