This file provides a solution to the common graph problem of finding the Single Source Shortest Path, through the implementation of Dijkstra's algorithm. Before diving into the actual algorithm's implementation, it is necessary to provide a basic implementation of two ADTs: a graph, and a min-heap. The graph is implemented as a weighted, directed graph, and the min-heap is implemented as a priority queue.

The graph is represented through three families of dynamic facts asserted into the Prolog knowledge base:

• graph/1: identifies a graph by name.
• vertex/2: associates a vertex to its graph.
• arc/4: associates a directed, weighted arc to its graph, source vertex, destination vertex, and weight.

The predicate new_graph(G) succeeds when a graph identified by G already exists in the knowledge base (cutting after the first clause), or otherwise asserts a new graph(G) fact.

Complexity: $f(n) \sim \Theta(1)$

This predicate always succeeds (due to the use of retractall/1), and wipes the graph identified by G, along with all associated vertex/2 and arc/4 facts, from the knowledge base.

Complexity: $f(n) \sim O(V + E)$, where $V$ is the number of vertices and $E$ is the number of arcs.

This predicate succeeds when the graph G exists in the knowledge base and the vertex V is not already present in it. It then asserts a new vertex(G, V) fact at the end of the knowledge base via assertz/1.

Complexity: $f(n) \sim O(V)$, due to the membership check \+ vertex(G, V).

This predicate uses findall/3 to collect all vertices V such that vertex(G, V) holds, unifying the result with Vs.

Complexity: $f(n) \sim O(V)$

This predicate succeeds when the graph G exists, both endpoint vertices U and V exist in G, and no arc between them is already present. It then asserts a new arc(G, U, V, Weight) fact.

Complexity: $f(n) \sim O(E)$, due to the membership check \+ arc(G, U, V, _).

This predicate uses findall/3 to collect all arcs of the form arc(G, U, V, Weight) such that the corresponding fact holds in the knowledge base.

Complexity: $f(n) \sim O(E)$

This predicate uses findall/3 to collect all vertices N such that a direct arc arc(G, V, N, _) exists.

Complexity: $f(n) \sim O(E)$

The priority queue needed by Dijkstra's algorithm is implemented as a min-heap. The heap is represented through two families of dynamic facts:

• heap/2: stores the heap identifier and its current size.
• heap_entry/4: stores each element as a quadruple heap_entry(H, Position, Key, Value), where Position encodes the node's location in the logical binary tree.

The binary tree structure is navigated arithmetically: for a node at position $i$, its parent is at $\lfloor i/2 \rfloor$, its left child at $2i$, and its right child at $2i + 1$.

The predicate new_heap(H) succeeds when a heap identified by H already exists in the knowledge base (cutting after the first clause), or otherwise asserts a new heap(H, 0) fact, initializing the size to zero.

Complexity: $f(n) \sim \Theta(1)$

This predicate always succeeds and wipes the entire heap identified by H from the knowledge base, using retractall/1 to remove all heap_entry/4 facts and the heap/2 fact itself.

Complexity: $f(n) \sim O(n)$, where $n$ is the number of elements in the heap.

This predicate succeeds when S is unified with the size of the heap identified by H, directly by unifying with the heap(H, S) fact.

Complexity: $f(n) \sim \Theta(1)$

The predicate empty/1 succeeds when the heap identified by H has size 0. Conversely, not_empty/1 succeeds when the heap size is anything other than 0, verified via \+ heap_size(H, 0).

Complexity: $f(n) \sim \Theta(1)$

This predicate succeeds when the heap identified by H is not empty and the heap_entry fact at position 1 (the root of the logical binary tree) exists, unifying K and V with its key and value respectively.

Complexity: $f(n) \sim \Theta(1)$

This predicate succeeds when, after a new element V with key K is appended to the heap H at the next available position (i.e., NewS = OldS + 1), the heap property is restored by calling the helper heapify_up/2.

Complexity: $f(n) \sim O(\log n)$

This predicate restores the min-heap property after an insertion by bubbling the newly inserted element upward until its key is no longer smaller than its parent's key. It is structured in three clauses:

$$T(n) = \begin{cases} \Theta(1) & \text{if } P = 1 \quad \textbf{(Base Case A: root reached)} \\ \Theta(1) & \text{if } \text{key}(P) \geq \text{key}(\lfloor P/2 \rfloor) \quad \textbf{(Base Case B: heap property respected)} \\ T(P/2) + \Theta(1) & \text{otherwise} \quad \textbf{(Recursive Case: swap and recurse upward)} \end{cases}$$

Complexity: $f(n) \sim O(\log n)$, since the height of the heap is $\lfloor \log_2 n \rfloor$.

This predicate succeeds when the root element (the minimum) of heap H is removed and returned, after which the heap property is restored. It is structured in two clauses:

• Clause A: the heap contains exactly one element: the root heap_entry(H, 1, K, V) is simply retracted and the heap size is set to 0.
• Clause B: the heap contains more than one element: the root is retracted, the last element is moved to position 1, the heap size is decremented, and heapify_down/2 is called to restore the min-heap property.

Complexity: $f(n) \sim O(\log n)$

This predicate implements a logic version of the MIN-HEAPIFY procedure from [[Introduction To Algorithms — T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein]]. It pushes the element at position ParentP downward until the heap property is restored. It is structured in two clauses:

$$T(n) = \begin{cases} \Theta(1) & \text{if no minor child exists, or } \text{key}(\text{ParentP}) \leq \text{key}(\text{ChildP}) \quad \textbf{(Base Case)} \\ T(2n) + \Theta(1) & \text{otherwise} \quad \textbf{(Recursive Case: swap and recurse downward)} \end{cases}$$

Complexity: $f(n) \sim O(\log n)$

This predicate determines which of the two children of a node at ParentP has the smaller key, unifying ChildP with the position of the minor child. It is structured in three clauses:

• Clause A: both children exist and the left child's key is $\leq$ the right child's key: ChildP is unified with the left child's position.
• Clause B: both children exist and the right child's key is strictly $<$ the left child's key: ChildP is unified with the right child's position.
• Clause C: only the left child exists (i.e., the right child's position exceeds the heap size): ChildP is unified with the left child's position.

Complexity: $f(n) \sim \Theta(1)$

This predicate succeeds when the element at ParentP has a key strictly greater than the element at ChildP, indicating that a swap is necessary to maintain the min-heap property. It relies on the key_less/2 predicate to handle inf-safe comparisons.

Complexity: $f(n) \sim \Theta(1)$

This predicate swaps the heap_entry facts at positions AP and BP within heap H by retracting both entries and re-asserting them with their positions exchanged.

Complexity: $f(n) \sim \Theta(1)$

These predicates implement inf-safe key comparisons, handling the special symbolic value inf which represents an infinite distance in the SSSP context:

• key_less(A, inf) always succeeds (any finite key is less than infinity).
• key_less(inf, _) always fails (infinity is never less than anything).
• key_less(A, B) falls through to arithmetic A < B for finite values.

key_leq/2 follows the same logic, using =< for finite comparisons.

Complexity: $f(n) \sim \Theta(1)$

This predicate replaces the key OldKey associated with value V in heap H with a new key NewKey, then restores the heap property. It is structured in three clauses:

• Case A (OldKey = inf): retracts the entry with key inf, asserts the new key, and calls heapify_up/2, since any finite key is smaller than infinity.
• Case B (NewKey =< OldKey): retracts the old entry, asserts the new key, and calls heapify_up/2, since decreasing a key may violate the heap property upward.
• Case C (NewKey > OldKey): retracts the old entry, asserts the new key, and calls heapify_down/2, since increasing a key may violate the heap property downward.

Complexity: $f(n) \sim O(\log n)$

This predicate prints the internal state of the heap to the Prolog console by first printing the heap/2 fact and then iterating over all entries via the helper print_node/3.

Complexity: $f(n) \sim O(n)$

The Single Source Shortest Path is computed via Dijkstra's algorithm, using the min-heap defined above as the priority queue. The algorithm's state is stored in three families of dynamic facts:

• distance/3: stores the current best-known distance from the source to each vertex.
• previous/3: stores the predecessor of each vertex on the shortest path tree.
• visited/2: marks vertices that have already been extracted from the priority queue.

This is the main entry point for the algorithm. It proceeds in four steps:

1. Verifies that the graph G and source vertex Source exist.
2. Calls initialize_single_source/2 to set all distances to inf and the source distance to 0.
3. Creates a fresh heap and fills it with all vertices, keyed by their initial distances.
4. Calls shortest_subpath/2 to run the main Dijkstra loop.

Complexity: $f(n) \sim O((V + E) \cdot \log V)$, where $V$ is the number of vertices and $E$ is the number of arcs.

This predicate initializes the algorithm's state by retracting all existing distance/3, previous/3, and visited/2 facts, then setting every vertex's distance to inf via init_distances/2, and finally setting the source vertex's distance to 0 via change_distance/3.

Complexity: $f(n) \sim O(V)$

This predicate recurses over the list of vertices, asserting distance(G, V, inf) for each vertex.

$$T(n) = \begin{cases} \Theta(1) & \text{if } Vs = [] \quad \textbf{(Base Case)} \\ T(n-1) + \Theta(1) & \text{otherwise} \quad \textbf{(Recursive Case)} \end{cases}$$

Complexity: $f(n) \sim O(V)$

This predicate recurses over the list of vertices, inserting each one into the heap keyed by its current distance (initially inf for all vertices except the source, which is 0).

$$T(n) = \begin{cases} \Theta(1) & \text{if } Vs = [] \quad \textbf{(Base Case)} \\ T(n-1) + O(\log n) & \text{otherwise} \quad \textbf{(Recursive Case: insert into heap)} \end{cases}$$

Complexity: $f(n) \sim O(V \log V)$

This predicate implements the main loop of Dijkstra's algorithm. At each step it extracts the vertex U with the minimum distance from the priority queue, marks it as visited, collects all unvisited neighbors of U, and calls relax_neighbors/4 to potentially update their distances.

$$T(n) = \begin{cases} \Theta(1) & \text{if the heap is empty} \quad \textbf{(Base Case)} \\ T(n-1) + O(\deg(U) \cdot \log V) & \text{otherwise} \quad \textbf{(Recursive Case)} \end{cases}$$

Complexity: $f(n) \sim O((V + E) \log V)$

This predicate recurses over the list of unvisited neighbors of vertex U, calling relax/4 for each one.

$$T(n) = \begin{cases} \Theta(1) & \text{if } Ns = [] \quad \textbf{(Base Case)} \\ T(n-1) + O(\log V) & \text{otherwise} \quad \textbf{(Recursive Case)} \end{cases}$$

Complexity: $f(n) \sim O(\deg(U) \cdot \log V)$

This predicate attempts to relax the edge $(U, V)$ i.e., to update the distance to V if the path through U is shorter than the current best-known distance. It is structured in three clauses:

• Case A:U's distance is inf: no relaxation is possible, the predicate cuts immediately.
• Case B: the new distance DU + W is shorter than V's current distance: modify_key/4 is called to update V's key in the heap, and change_distance/3 and change_previous/3 update the knowledge base accordingly.
• Case C: the new distance is not an improvement: the predicate succeeds trivially without modifying anything.

Complexity: $f(n) \sim O(\log V)$ per call (dominated by modify_key/4).

This predicate succeeds when NewD represents a strictly shorter distance than OldD. It is structured in two clauses:

• Case A: OldD = inf: any finite distance is always shorter than infinity.
• Case B: both distances are finite: standard arithmetic comparison NewD < OldD.

Complexity: $f(n) \sim \Theta(1)$

This predicate reconstructs the shortest path from Source to V by following the previous/3 chain backwards. It is structured in two clauses:

• Base Case: Source = V: the path is empty (no arcs needed to reach the source from itself).
• Recursive Case: looks up V's predecessor U via previous/3, retrieves the arc connecting them, recursively builds the path to U, and appends the arc arc(G, U, V, W) to it.

$$T(n) = \begin{cases} \Theta(1) & \text{if } V = Source \quad \textbf{(Base Case)} \\ T(n-1) + O(n) & \text{otherwise} \quad \textbf{(Recursive Case: append arc)} \end{cases}$$

Complexity: $f(n) \sim O(V^2)$ in the worst case due to repeated append/3 calls. This can be reduced to $O(V)$ using a difference-list approach or by reversing the accumulated path at the end.

These predicates update the knowledge base by retracting all existing distance/3 (or previous/3) facts for vertex V in graph G and asserting the new value. The use of retractall/1 guarantees that no stale facts remain.

Complexity: $f(n) \sim \Theta(1)$ (at most one fact exists per vertex at any time).