Write a C$++$ Program following these instructions: $-$"palomarMapEdge.txt$"$ data format: ID$,$ building name, x & y coordinates $($use for vertex$),$ and then all the adjacent vertices$/$ buildings that are connected to the building$($use to create edges$).$ Here are the $1$st $2$ lines of the text file as an ex: $1,$Lot #$12,77\mathrm{.}0727,-217\mathrm{.}6818,$Parking Structure,PD$,$Lot #$13$

$2,$Lot #$5,21\mathrm{.}2657,162\mathrm{.}7727,$Lot #$7$A$,$NS$,$PL$,$Closed,Arboretum

$-$Read the text file "palomarMapEdge.txt$"$ into a matrix. Generate matrix.

Adjacency Matrix Representation $$ In this representation, each graph of n nodes is represented by an n x n matrix A$,$ that is$,$ a two$-$dimensional array A $$ The nodes are $($re$)-$labeled $1,2,...,$n $$ A$[$i$][$j$]=1$ if $($i$,$j$)$ is an edge $$ A$[$i$][$j$]=0$ if $($i$,$j$)$ is not an edge

$-$Create a vertex for each building using the coordinates provided. Each vertex should also have $2$ data members: ID and building name

$-$Create edges for all the connected buildings, weights, and calculate distance between them using standard distance formula

$-$Generate into a weighted, undirected graph$/$ campus map

$$ A graph G is represented as G $=($V$,$ E$)$

$$ V is a set of vertices

$$ E is a set of edges

$$ Operations include:

$$ iterating over vertices

$$ iterating over edges

$$ iterating over vertices adjacent to a specific vertex

$$ asking whether an edge exists connected two vertices

$-$Weighted Graph: $$ Same as above, but where each edge also has an associated real number with it$,$ known as the edge weight.

$-$ A weighted graph $$ A weighted graph associates a label $($weight$)$ with every edge in the graph. $$ The weight of a path or the weight of a tree in a weighted graph is the sum of the weights of the selected edges.

$-$Undirected graphs are connected if there is a path between any two vertices

$-$Call constructor to generate a graph from the matrix

Traverse graph using either depth first traversal or bredth first traversal & find shortest path using Dijkstra's algorithm. A path $$ A path of length n from vertex v$0$ to vertex vn is an alternating sequence of n$+1$ vertices and n edges beginning with vertex v$0$ and ending with vertex vn in which edge ei is incident upon vertices vi$-1$ and vi $.($The order in which these are connected matters for a path in a directed graph in the natural way.$)$

Breadth$-$First Search $$ BFS follows the following rules: $1.$ Select an unvisited node x$,$ visit it$,$ have it be the root in a BFS tree being formed. Its level is called the current level. $2.$ From each node z in the current level, in the order in which the level nodes were visited, visit all the unvisited neighbors of z$.$ The newly visited nodes from this level form a new level that becomes the next current level. $3.$ Repeat step $2$ until no more nodes can be visited. $4.$ If there are still unvisited nodes, repeat from Step $1.$ CS $10335$ Implementation of BFS $$ Observations: $$ The first node visited in each level is the first node from which to proceed to visit new nodes. $$ This suggests that a queue is the proper data structure to remember the order of the steps. Breadth$-$First Traversal $$ Use a queue to store set of vertices to be visited $$ Visit all neighbors before visiting any of their neighbors Breadth$-$First Implementation $$ Uses a queue of vertex numbers $$ The start vertex is processed, marked, placed in the queue $$ Repeat until queue is empty: $$ remove a vertex v from the queue $$ for each unmarked neighbor u of v: process u$,$ mark u$,$ place u in the queueBFS $($Pseudo Code$)$ BFS$($input: graph G$)\{$ Queue Q; Integer x$,$ z$,$ y; while $($G has an unvisited node x$)\{$ visit$($x$)$; Enqueue$($x$,$Q$)$; while $($Q is not empty$)\{$ z :$=$ Dequeue$($Q$)$; for all $($unvisited neighbor y of z$)\{$ visit$($y$)$; Enqueue$($y$,$Q$)$; $\}\}\}\}$

Dijkstra's algorithm $$ Dijkstra's algorithm: finds shortest $($minimum weight$)$ path between a particular pair of vertices in a weighted directed graph with nonnegative edge weights $$ solves the "one vertex, shortest path" problem $$ basic algorithm concept: create a table of information about the currently known best way to reach each vertex $($distance$,$ previous vertex$)$ and improve it until it reaches the best solution Dijkstra pseudocode Dijkstra$($v$1,$ v$2)$: for each vertex v: $//$ Initialization v$\text{'}$s distance :$=$ infinity. v$\text{'}$s previous :$=$ none. v$1\text{'}$s distance :$=0.$ List :$=\{$all vertices$\}.$ while List is not empty: v :$=$ remove List vertex with minimum distance. mark v as known. for each unknown neighbor n of v: dist :$=$ v$\text{'}$s distance $+$ edge $($v$,$ n$)\text{'}$s weight. if dist is smaller than n$\text{'}$s distance: n$\text{'}$s distance :$=$ dist. n$\text{'}$s previous :$=$ v$.$ reconstruct path from v$2$ back to v$1,$ following previous pointers.

$-$Output: have user enter source ID and sink ID $($assign ID$$s to building locations$)$ & then calculate and print the shortest path A VISUAL REPRESENTATION OF THE ACTUAL PATH TAKEN EITHER BY SHOWING THE VERTICES ALONG THE PATH, THE BUILDING ALONG THE PATH, THE EDGE INFO PRINTED, ETC. SOMETHING TO PROVE THE SHORTEST PATH TAKEN.