Build a graph with an adjacency list Use Dijkstra’s algorithm to find best paths

Build a graph with an adjacency list

Use Dijkstra’s algorithm to find best paths

Code in Object Oriented C++

Use of File IO

Outcomes:

Identify, construct, and clearly define a data structure that is useful for modeling a given problem.

State some fundamental algorithms such as merge sort, topological sort, prim’s and Kruskal’s algorithm, and algorithmic techniques such as dynamic programming and greedy algorithms

Combine fundamental data structures and algorithmic techniques in building a complete algorithmic solution to a given problem

Design an algorithm to solve a given problem

Description

This project is going to build directed & undirected weighted graphs then search them using Dijkstra’s algorithm to find best paths between nodes.

Instructions:

This program will have you build on the Adjacency Matrix you previously completed. You will be adding Dijkstra’s Algorithm functionality to it.

And make use of Data Structures you’ve coded in the past:

MatrixGraph

Linked List

MinHeap/MaxHeap

Stack

Arrays

You will be building a Graph Data Structure using the Adjacency Matrix method. It will read the topology of the graph from a file then build the vertices and edges.

The user will then be given an interface to perform searches on the graph from specified starting nodes and goal nodes.