 Dijkstra's Algorithm in C++

Subject Computer Science Data Structures and Algorithms

Question

Check the file: Questions.pdf

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

#include "city_map.h"
#include <iostream>
#include <string>
#include <sstream>
#include <map>
#include <list>
#include <math.h>
#include <vector>

using namespace std;

// return square of a number
double sqr(double x)
{
return x * x;
}
//constructor
City_Map::City_Map()
{
string str;
int maxAvenue = 0; //max number of avenues
int maxStreet = 0; // max number of streets

while (getline(cin, str)) // read a line from standard input
{
stringstream s;
s << str;
// parse the string into intersection
Intersection *is = new Intersection;
s >> is->street;
s >> is->avenue;
s >> is->x;
s >> is->y;
s >> is->green;
s >> is->green;
all.push_back(is); // add intersection to the list
if ((is->avenue == 0) && (is->street == 0)) // check if it is the start point
{
first = is;
}
if ((is->avenue > maxAvenue) || ((is->avenue == maxAvenue) && (is->street > maxStreet))) // check if it is the last point
{
maxAvenue = is->avenue;
maxStreet = is->street;
last = is;
}
}
vector<vector<Intersection*>> iv; // create a matrix of intersections, to easily reach the neighbour nodes
iv.resize(maxStreet + 1);
for (int i = 0; i <= maxStreet; i++)
{...

This is only a preview of the solution. Please use the purchase button to see the entire solution

Related Homework Solutions

Greedy Strategy Programming Problem \$10.00
Computer Science
Programming
Greedy Strategy
Algorithms
Company
Workers
Properties
Sets
Shifts
Intervals
Variables
Statements
Sequences
Complexity
Finish Time
Input
Output
Nondeterministic Algorithm for K-Clique Problem \$10.00
NP
Nondeterministic
Deterministic
Algorithm
K-Clique
Polynomial
Time
NP-Hard
NP-Complete
P
Computer Science
Data Structures
Implementation of the Deque ADT Using a Circularly Linked List \$50.00
Implementation
Deque
C Language
Computer
Science
Data
Structures
Algorithms
5 Problems Involving Greedy Algorithms \$50.00
Greedy
Algorithm
Analysis
Optimal
Program
Disk
Megabyte
Storage
Capacity
Decimalization
Denomination
Change-making
Half-crown
Florin
Shilling
Sixpence
Threepence
Pence
Coin
Solution
Selection
Sort
Framework
Decomposition
Egyptian
Huffman Coding Java Implementation and Performance Report \$35.00
Huffman
Coding
Report
Symbol
Frequency
Binary
Code
Prefix
Weighted
Length
Chart
Complexity
Java
Algorithm
Path
Tree
Live Chats