Reading 10: Dijkstra's Algorithm, Minimum Spanning Tree

Readings

The readings for Monday, November 14 are:

Data Structures and Other Objects Using C++:
- 15.4
Data Structures & Algorithm Analysis
- 11.4 - 11.5
Algorithms

TL;DR

The focus of the reading is graph algorithms, specifically Kahn's Algorithm for topological sorting, Dijkstra's Algorithm for single-source shortest path and Prim's Algorithm for computing a minimum spanning tree.

Questions

Once you have completed the readings, answer the following questions in the reading10/README.md file in your assignments repository:

What exactly is:

A. A Topological Sorting? What is a real world application of this?

B. A Single-Source Shortest Path? What is a real world application of this?

C. A Minimum Spanning Tree? What is a real world application of this?
Given a graph, is it possible to have more than one:

A. Topological Sorting?

B. Single-Source Shortest Path?

C. Minimum Spanning Tree?

Briefly explain why or why not.
For each of the following graphs:

A. Use Kahn's Algorithm to compute a topological sort of the nodes.

For instance, Graph 0 could have the following topological sorting:
```
A, C, B, E, D, F
```
B. Use Dijkstra's Algorithm to compute the shortest path from A to every other node.

For instance, Graph 0 could have the following spanning tree:
```
(A, C)
(C, B)
(C, E)
(D, F)
(E, D)
```
C. Use Prim's Algorithm to compute the minimum spanning tree (assume the edges are undirected).

For instance, Graph 0 could have the following minimum spanning tree:
```
(A, C)
(B, C)
(C, E)
(D, E)
(D, F)
```

Submission

To submit your solution, you must initiate a Merge Request in your private assignments repository and assign it to the appropriate TA from the Reading 10 - TA assignment list.

Development Branch

To facility the Merge Request workflow, you must do your development in its own branch:

$ cd path/to/repo                 # Go to your repository
$ git checkout master             # Make sure we are on master branch first
$ git pull                        # Make sure we have changes from GitLab
$ git checkout -b reading10       # Create reading10 branch
...                               # Do your work
$ git commit                      # Commit your work (can do this multiple times)
$ git push -u origin reading10    # Push branch to GitLab