Lab #6: Dijkstra’s Shortest-Path Tree

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
#----------------------------------------------------------

Only one team member needs to upload the file.

Due date is Tuesday, October 18.