Dijkstra's Algorithm

Dijkstra's Algorithm

Dijkstra’s algorithm is for finding the single source shortest path from a starting node to all the other nodes in a connected graph of non-negative weights.

This algorithm operates on the principle of relaxation, where it initially overestimates the distances from each node to the source node, setting these distances as an upper bound.

The distance is calculated as the sum of all the edges from the source node to the particular node.

As a new edge is visited, new paths are found as outgoing edges to other nodes. The distance to these outgoing nodes is updated as the minimum of the old path length and the new path length, thus lowering the upper bound as the estimate of the shortest distance.

The visited node will be added to our set of visited node and the distance distance of the visited node is the distance of the shortest path from the source node.

Dijkstra separates the nodes into visited nodes and unvisited nodes. The frontier nodes are a set of unvisited nodes that act as the barrier between the visited nodes and the other unvisited node. We keep track of the frontier node with the minimum distance and add that node to our set of visited nodes. The distance of the visited node is the shortest distance from the source node because any path from the visited nodes to the unvisited nodes must pass through the frontier nodes and the node that we added to the visited node has the smallest distance.

Frontier Node: An unvisited node that is an edge away from a visited node.

Algorithm

We will use a set to keep track of the visited node. Once a node has been visited we will put the node in the set.

Visited node

A map is used to store distances from the source, initially set to infinity for all nodes.

Step 1: Initialize the distance of the starting node to 0 and all the other nodes to infinity.

Step 2: Visit the source node. For all the adjacent nodes that is at the end of the outgoing edges of the source node that hasn’t been visited:

  • Calculated the distance of the visited node + the outgoing edge
  • Update the distance of the adjacent node if the distance of the visited node + the outgoing edge is less than the current distance of the adjacent node.

Then mark the source node as visited.

Step 3: Select the unvisited node with the smallest distance and repeat Step 2 with that node. Continues untill all the nodes has been visited.

Note: As each node is visited, the set of unvisited nodes shrinks, breaking the problem into smaller subproblems.

Note: By marking nodes as visited and excluding them from future checks, the algorithm avoids unnecessary backtracking.

Triangle Inequality

The effectiveness of Dijkstra’s algorithm is based on the triangle inequality, which ensures that the path found is the shortest.

For example, if the direct path from node 0 to node 3 is 6 units (d=6(0->3)) is the shourtest then any alternative route must go through the other frontier nodes eg (d=7(0->1->2)), and since node 3 is the shortest route to any frontier node then:

  • d=6(0->3) < d=7(0->1->2)
  • d=6(0->3) <= d=7(0->1->2) + d=14(0->1->2->3)
  • d=6(0->3) <= d=M (path to any frontier node) + d=N (distance to any unvisited node)

This illustrates that the shortest path does not involve detours through additional nodes, validating the distances updated and maintained throughout the algorithm’s execution.

from typing import Union, List, Tuple, Dict
from collections import defaultdict
import heapq

Node = Union[int, str]

class Dijkstra:
    def __init__(self, edges: List[Tuple[Node, Node, int]]) -> None:
        self.adjacent_map = self.__initialize_adjacent_map(edges)
        self.distances = self.__initialize_distances(self.adjacent_map)

    def __initialize_adjacent_map(self, edges: List[Tuple[Node, Node, int]]) -> Dict[Node, List[Tuple[Node, int]]]:
        adjacent_map = defaultdict(list)
        for node1, node2, weight in edges:
            adjacent_map[node1].append((weight, node2))
            adjacent_map[node2].append((weight, node1))  # Assuming the graph is undirected
        return dict(adjacent_map)

    def __initialize_distances(self, adjacent_map: Dict[Node, List[Tuple[Node, int]]]) -> Dict[Node, int]:
        distances = {}
        for node in adjacent_map.keys():
            distances[node] = float('inf')
        return distances

    def find_shortest_path(self, start_node: Node) -> Dict[Node, int]:
        # This method would implement Dijkstra's algorithm to find the shortest path
        # from start_node to all other nodes. This method should return a dictionary
        # mapping nodes to their shortest distance from start_node.
        distances = self.distances.copy()
        visited_nodes = set()
        min_heap = []
        
        distances[start_node] = 0
        heapq.heappush(min_heap, (0, start_node))

        while min_heap:
            current_node_distance, current_node = heapq.heappop(min_heap)
            if current_node not in visited_nodes:
                for adjacent_node_edge_length, adjacent_node in self.adjacent_map[current_node]:
                    distances[adjacent_node] = min(distances[adjacent_node], current_node_distance + adjacent_node_edge_length)
                    heapq.heappush(min_heap, (distances[adjacent_node], adjacent_node))
            visited_nodes.add(current_node)

        return distances        
edges = [
    (0, 1, 2),
    (0, 3, 6),
    (1, 2, 5),
    (2, 3, 7),
    (2, 5, 9),
    (2, 4, 6),
    (3, 4, 10),
    (5, 4, 6)
]
dijkstra = Dijkstra(edges)

dijkstra.find_shortest_path(0)        

Limitation of Dijkstra’s Algorithm with Negative?Weights


The algorithm relies fundamentally on the assumption that once the shortest path to a node is determined, it will not change. This is because each successive step in Dijkstra’s algorithm builds on the previous steps, assuming that the previously calculated shortest paths are correct and final.

The algorithm relies that distance of the visited node is the distance from the shortest path from the source node. This is supported by the triangle inequality in which the path of the selected node is the shortest. Any alternative route that tries to reach this node through another frontier node will inherently have a greater distance because it must include the additional path length from the other frontier node to the selected node.

The presence of negative weights disrupts this assumption. A negative weight is sufficiently small that a detour via another frontier node to the visited node could result in a shorter path than previously determined.

Difference between Prims and?Dijkstra


The Dijkstra and Prims algorithm look similar, because they both perform breadth first search and select the minimum distances of unvisited nodes. Lets look at the difference between them.

  • Prims Algorithm: Used to find the minimum spanning tree (MST) in a weighted, undirected graph. It starts from any node and expands the tree by adding the nearest unvisited node at each step, ensuring all nodes are connected with the minimum possible total edge weight.
  • Dijkstra Algorithm: Used to find the shortest path from a single source to all other nodes in a graph with non-negative weights. It calculates the shortest path by continuously updating the cumulative cost to reach each node from the source, selecting the node with the smallest known distance at each step.

Distance Calculation:

  • Prims: The distance tracked for each node is the minimum edge weight by which it can be connected to the growing MST. It only considers the weight of the connecting edge from the MST to a new node.
  • Dijkstra: The distance for each node is the sum of the weights from the source node along the shortest path found so far. It accumulates total path weights from the source to each node.

Prims algorithm gives the tree where all the nodes are connected and the sum of the weights of the edges that connect the node is minimum.

Dijkstra provide the shortest route from the source to each node.

I’d like to thank the following resources which were referenced in this article:

要查看或添加评论,请登录

Yi leng Yao的更多文章

  • Introduction to MCP in?Java

    Introduction to MCP in?Java

    Model Context Protocol (MCP) is a standard that allows a language models (LLMs) access to tools, resources, and…

  • Building AI Chat Agent with LLMTools and State?Machines

    Building AI Chat Agent with LLMTools and State?Machines

    Motivation I want to create an AI Chat Agent using LLMTools(LLM Function Calling in Java with LLMTools) and InnoBridge…

    2 条评论
  • Creating Distributed State Machines in Java

    Creating Distributed State Machines in Java

    Motivation I want a framework to model complex business processes by breaking them down into simpler steps. Creating my…

  • LLM Function Calling in Java with?LLMTools

    LLM Function Calling in Java with?LLMTools

    Motivation The flow of logic in traditional software is deterministic, meaning that the same input always produces the…

  • Setup Your Remote AI Server

    Setup Your Remote AI Server

    Motivation This is a followup article on How To Build Your Own AI Powered PC, once my PC has been build, I want to off…

  • How To Build You Own AI Powered?PC

    How To Build You Own AI Powered?PC

    Motivation I want to make API calls to LLM models without getting charge for heavy usage and run experiments on LLM…

  • Run LLMs Natively in your Java Application

    Run LLMs Natively in your Java Application

    Motivation When developing a Java application that utilizes Large Language Models (LLMs), relying on external API calls…

    2 条评论
  • Integrate Jupyter Notebook with AI for Free

    Integrate Jupyter Notebook with AI for Free

    Motivation A couple of months ago, I discovered Pretzel, a library that allows me to run code completion and…

  • Bootstrapping your Application with InnoBridge Security

    Bootstrapping your Application with InnoBridge Security

    Motivation InnoBridge Security simplifies the implementation of security in your application by reducing the need for…

  • Publishing Your Java Library to Maven Central Using GitHub?Actions

    Publishing Your Java Library to Maven Central Using GitHub?Actions

    Motivation Publishing your library to Maven Central allows you to easily share it with other users. This article…

    2 条评论

社区洞察

其他会员也浏览了