# Lab #6: Dijkstra’s Shortest-Path Tree

### Objective

During this activity, students will be able to:

• Implement Dijkstra’s algorithm in order to build a graph’s shortest-path tree starting in a given vertex.

## Description

This activity must be developed in the pre-assigned teams of two.

In a file called dijkstra.py, write a Python function called dijkstra_spt that takes as input an initial vertex and a connected undirected weighted graph. The function uses Dijkstra’s algorithm to find the shortest-path between the initial vertex and all the other graph’s vertices. The function returns a tuple with two items:

1. A costs dictionary where each key $$k$$ is a vertex and its associated value is the cost of going from the initial vertex to the vertex $$k$$.
2. The resulting spanning tree with the shortest-path from the initial vertex to every other one.

For example, given the following weighted graph:

The resulting costs dictionary with initial vertex A is:

Vertex Cost
A 0
B 5
C 8
D 7
E 6

The graph that represents the shortest-path spanning tree is:

This is how the dijkstra_spt function should be called:

dijkstra_spt('A', {'A': {('B', 5), ('C', 10), ('E', 6)},
'B': {('A', 5), ('D', 2)},
'C': {('A', 10), ('D', 1), ('E', 3)},
'D': {('B', 2), ('C', 1), ('E', 4)},
'E': {('A', 6), ('C', 3), ('D', 4)},
})


Note that strings are used to represent the vertices, while the graph is represented as a dictionary where each key is a string and its associated value is a set of tuples (the vertex’s neighbours) containing a string and a number (the respective edge’s weight).

The previous function call returns the following result:

({'A': 0, 'B': 5, 'C': 8, 'D': 7, 'E': 6},
{'A': {('B', 5), ('E', 6)},
'B': {('A', 5), ('D', 2)},
'C': {('D', 1)},
'D': {('B', 2), ('C', 1)},
'E': {('A', 6)}})


Use the following code as a starting point:

# File: dijkstra.py

WeightedGraph = dict[str, set[tuple[str, float]]]

def dijkstra_spt(
initial: str,
graph: WeightedGraph) -> tuple[dict[str, float], WeightedGraph]:
# The function's code goes here
...


Test your program using the following unit tests:

# File: dijkstra_spt_test.py

from unittest import TestCase, main
from dijkstra import dijkstra_spt, WeightedGraph

biggie: WeightedGraph = {
'A': {('B', 4), ('E', 8)},
'B': {('A', 4), ('E', 11), ('C', 8)},
'C': {('B', 8), ('I', 2), ('G', 4), ('D', 7)},
'D': {('C', 7), ('G', 14), ('H', 9)},
'E': {('A', 8), ('B', 11), ('I', 7), ('F', 1)},
'F': {('E', 1), ('I', 6), ('G', 2)},
'G': {('F', 2), ('C', 4), ('D', 14), ('H', 10)},
'H': {('D', 9), ('G', 10)},
'I': {('C', 2), ('E', 7), ('F', 6)},
}

class Testdijkstra_spt(TestCase):

def test_dijkstra_spt_1(self):
self.assertEqual(
({'A': 0, 'B': 1},
{'A': {('B', 1)},
'B': {('A', 1)}}),
dijkstra_spt('A', {
'A': {('B', 1)},
'B': {('A', 1)}
}))

def test_dijkstra_spt_2(self):
self.assertEqual(
({'A': 0, 'B': 1, 'C': 1},
{'A': {('B', 1), ('C', 1)},
'B': {('A', 1)},
'C': {('A', 1)}}),
dijkstra_spt('A', {
'A': {('B', 1), ('C', 1)},
'B': {('A', 1), ('C', 2)},
'C': {('A', 1), ('B', 2)},
}))

def test_dijkstra_spt_3(self):
self.assertEqual(
({'A': 1, 'B': 1, 'C': 1, 'D': 1, 'E': 0},
{'A': {('E', 1)},
'B': {('E', 1)},
'C': {('E', 1)},
'D': {('E', 1)},
'E': {('A', 1), ('B', 1), ('C', 1), ('D', 1)}}),
dijkstra_spt('E', {
'A': {('B', 1), ('C', 1), ('D', 1), ('E', 1)},
'B': {('A', 1), ('C', 1), ('D', 1), ('E', 1)},
'C': {('A', 1), ('B', 1), ('D', 1), ('E', 1)},
'D': {('A', 1), ('B', 1), ('C', 1), ('E', 1)},
'E': {('A', 1), ('B', 1), ('C', 1), ('D', 1)}
}))

def test_dijkstra_spt_4(self):
self.assertEqual(
({'A': 0, 'B': 1, 'C': 3, 'D': 6, 'E': 10},
{'A': {('B', 1)},
'B': {('A', 1), ('C', 2)},
'C': {('B', 2), ('D', 3)},
'D': {('C', 3), ('E', 4)},
'E': {('D', 4)}}),
dijkstra_spt('A', {
'A': {('B', 1)},
'B': {('A', 1), ('C', 2)},
'C': {('B', 2), ('D', 3)},
'D': {('C', 3), ('E', 4)},
'E': {('D', 4)}
}))

def test_dijkstra_spt_5(self):
self.assertEqual(
({'A': 6, 'B': 4, 'C': 5, 'D': 1, 'E': 0},
{'A': {('B', 2)},
'B': {('A', 2), ('D', 3)},
'C': {('E', 5)},
'D': {('B', 3), ('E', 1)},
'E': {('C', 5), ('D', 1)}}),
dijkstra_spt('E', {
'A': {('B', 2), ('C', 4)},
'B': {('A', 2), ('D', 3)},
'C': {('A', 4), ('E', 5)},
'D': {('B', 3), ('E', 1)},
'E': {('C', 5), ('D', 1)}
}))

def test_dijkstra_spt_6(self):
self.assertEqual(
({'A': 0, 'B': 5, 'C': 8, 'D': 7, 'E': 6},
{'A': {('B', 5), ('E', 6)},
'B': {('A', 5), ('D', 2)},
'C': {('D', 1)},
'D': {('B', 2), ('C', 1)},
'E': {('A', 6)}}),
dijkstra_spt('A', {
'A': {('B', 5), ('C', 10), ('E', 6)},
'B': {('A', 5), ('D', 2)},
'C': {('A', 10), ('D', 1), ('E', 3)},
'D': {('B', 2), ('C', 1), ('E', 4)},
'E': {('A', 6), ('C', 3), ('D', 4)},
}))

def test_dijkstra_spt_7(self):
self.assertEqual(
({'A': 0, 'B': 4, 'C': 12, 'D': 19, 'E': 8, 'F': 9,
'G': 11, 'H': 21, 'I': 14},
{'A': {('B', 4), ('E', 8)},
'B': {('A', 4), ('C', 8)},
'C': {('B', 8), ('D', 7), ('I', 2)},
'D': {('C', 7)},
'E': {('A', 8), ('F', 1)},
'F': {('E', 1), ('G', 2)},
'G': {('F', 2), ('H', 10)},
'H': {('G', 10)},
'I': {('C', 2)}}),
dijkstra_spt('A', biggie))

def test_dijkstra_spt_8(self):
self.assertEqual(
({'A': 19, 'B': 15, 'C': 7, 'D': 0, 'E': 14, 'F': 13,
'G': 11, 'H': 9, 'I': 9},
{'A': {('B', 4)},
'B': {('A', 4), ('C', 8)},
'C': {('B', 8), ('D', 7), ('G', 4), ('I', 2)},
'D': {('C', 7), ('H', 9)},
'E': {('F', 1)},
'F': {('E', 1), ('G', 2)},
'G': {('C', 4), ('F', 2)},
'H': {('D', 9)},
'I': {('C', 2)}}),
dijkstra_spt('D', biggie))

def test_dijkstra_spt_9(self):
self.assertEqual(
({'A': 21, 'B': 22, 'C': 14, 'D': 9, 'E': 13, 'F': 12,
'G': 10, 'H': 0, 'I': 16},
{'A': {('E', 8)},
'B': {('C', 8)},
'C': {('G', 4), ('B', 8), ('I', 2)},
'D': {('H', 9)},
'E': {('F', 1), ('A', 8)},
'F': {('E', 1), ('G', 2)},
'G': {('C', 4), ('H', 10), ('F', 2)},
'H': {('D', 9), ('G', 10)},
'I': {('C', 2)}}),
dijkstra_spt('H', biggie))

def test_dijkstra_spt_10(self):
self.assertEqual(
({'A': 14, 'B': 10, 'C': 2, 'D': 9, 'E': 7, 'F': 6,
'G': 6, 'H': 16, 'I': 0},
{'A': {('B', 4)},
'B': {('A', 4), ('C', 8)},
'C': {('B', 8), ('D', 7), ('G', 4), ('I', 2)},
'D': {('C', 7)},
'E': {('I', 7)},
'F': {('I', 6)},
'G': {('C', 4), ('H', 10)},
'H': {('G', 10)},
'I': {('C', 2), ('E', 7), ('F', 6)}}),
dijkstra_spt('I', biggie))

if __name__ == '__main__':
main()


Finally, make sure no type or PEP 8 style errors are produced by using the mypy and pycodestyle linters. You can incorporate these tools into VS Code or you can run them at the terminal.

## Deliverables

Place in a comment at the top of the dijkstra.py source file the authors’ personal information (student ID and name), for example:

#----------------------------------------------------------
# Lab #6: Dijkstra’s Shortest-Path Tree
#
# Date: 18-Oct-2022
# Authors:
#           A01770771 Kamala Khan
#           A01777771 Carol Danvers
#----------------------------------------------------------


To deliver the dijkstra.py file, please provide the following information: