Classic Dijkstra Algorithm

The Classic Dijkstra Algorithm is a fundamental algorithm for computing single-source shortest paths in weighted graphs, proposed by computer scientist Edsger W. Dijkstra in 1956. This algorithm applies to both directed and undirected graphs with non-negative edge weights, efficiently finding the shortest paths from a starting node to all other nodes in the graph.

### Core Algorithm Design Dijkstra's algorithm employs a greedy strategy, maintaining a priority queue (or min-heap) to select the node closest to the starting point for expansion. The key implementation steps include: Initialization: Set the distance from the start node to itself as 0, and to all other nodes as infinity. Iterative Relaxation: Extract the node with minimum distance from the priority queue, examine its adjacent nodes, and if a shorter path through the current node is found, update distances and enqueue the neighbor. Termination Condition: The algorithm terminates when the priority queue is empty, at which point all shortest paths from the source are determined.

### Implementation Applications Average Shortest Path: By running Dijkstra's algorithm multiple times from different sources, compute the average shortest path length between all node pairs to measure network compactness. Closeness Centrality: Calculate the average shortest path from each node to all others, reflecting a node's centrality in the network. Betweenness Centrality (Basic Version): Count the proportion of all shortest paths passing through a specific node, measuring its importance as a network bridge. Performance Optimization: Using efficient data structures like priority queues or Fibonacci heaps can significantly improve performance for large-scale graph computations.

### Algorithm Extensions Edge Betweenness: Similar to node betweenness but calculates the frequency of edges appearing in shortest paths. Bidirectional Search: Combining forward and reverse Dijkstra algorithms can accelerate path queries in specific scenarios.

Due to its simplicity and practicality, Dijkstra's algorithm serves as a fundamental tool in path planning and network analysis, with subsequent optimized algorithms (like A*) often building upon its core principles.