This assignment builds on the solution that you submitted for Lab #11 and uses the same friend network, but this time the friend relationships (edges) have weights, forming a directed, weighted graph.

The new data file is in the module here: fb_weighted.csv

Assignment

Write a program that prompts the user for two people as before, but outputs the lowest cost path between them.

The program should consider the friend edge weights between the ‘from’ person and the ‘to’ person and compute the cost of the path as well as be able to output the list of nodes and friend edges used:

The code in this file: fb_weights_starter.cpp adds some additional fields to the Person data structure starting with the example from Lab #11, and a new function dijkstra(), which implements the Dijkstra single-source shortest paths algorithm. The pseudocode for the algorithm is described on pages 653-654 of the textbook. After the function runs, two fields in the Person structure will contain current information and you can use this to output the best cost path and the edges used.

• The ‘best_parent’ field contains the string ID of the previous node used along the cheapest path to reach it (in other words, the “parent” node in the best path).
• The ‘best_weight’ field contains the cheapest cost (the sum of all the weights along this path).

The algorithm should stop when it locates the lowest path to the destination node.

After calulcating the best path, to complete the assignment add the remaining code in main() which should output the edges used in order — starting from the ‘from’ person and ending with the ‘to’ person.

Hint: if you start with the end node, you can rebuild the path backwards following each ‘best_parent’, then use a stack to reverse the output.

What to Submit

Submit only your .cpp file for the solution.

Example Input/Output

The output does not need to match exactly the example below, but should include at least the cost of the path and a list of the nodes used. Here are a few examples. Note that even though two people may have a direct connection (be friends), the cheapest path may take a different route. Here, Umar and Lema have a direct connection of weight 7, but the cheapest path is weight 4 and traverses 4 nodes.

Enter the starting name (X to quit): Umar

Enter the ending name (X to quit): Lema
The best path between these two people is: 
	Umar
	Saim Shah Hamdani
	Arwen
	Sara
	Lema
The cost of this path is: 4

Enter the starting name (X to quit): Tommy

Enter the ending name (X to quit): Amir
The best path between these two people is: 
	Tommy
	Mohsin Khan
	Dennis
	Umar Patek
	Amir
The cost of this path is: 5

Enter the starting name (X to quit): Gabriel

Enter the ending name (X to quit): Varga Melinda
There is NOT a path between these two people.

Enter the starting name (X to quit): X

Exiting...