COMP206-Graph-Traversal-and-Dijkstras-Algorithm

发表于 | 分类于
代写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 request. 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

1
2
3
4
5
6
7
8
9
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

1
2
3
4
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.