Single - Source SSP

Theorem

For a non - negative weighted graph, given vertices \(A\) and \(B \in S\), and any other vertex neighbor \(v \in S\) where the set \(S\) is the collection of all of the neighbor vertices of \(A\) in the graph. The \(\text{weight}(A,v)\) is the path weight directly from \(A\) to \(v\). We have:

Lemma: If \(\text{weight}(A,B)\) meets the condition for all \(v \in S\):

\[\text{weight}(A,B) \leq \text{weight}(A,v),\]

the global shortest path from \(A\) to \(B\) is the direct path from \(A\) to \(B\).

Tip

It can be improved to be Dijkstra’s Algorithm by replacing vertex \(A\) with the set \(S\).

Interface

Implement algorithms of BFS, dijkstra and xxxx in adjacency list graph.

class GNode(vertex: int, weight: int | float = inf)

Atomic element of the adjacency linked list.

__init__(vertex: int, weight: int | float = inf) → None

class AdjNode(vertex: int)

Atomic element of the adjacency list.

__init__(vertex: int) → None

class LGraph(num_vert: int)

Adjacency list graph

__init__(num_vert: int) → None

connect(v: int, w: int, weight: int = 1) → None

Connect the spcified vertex.

bfs(begin: int) → list

Unweight single source shortest path algorithms.

Parameters:

begin – The source vertex.

dijkstra(begin: int) → list