NeFut Logo NeFut
中 Admin Login

In-Depth Understanding of Single Source Shortest Path Algorithms: A Comprehensive Comparison of Dijkstra and SPFA

Published at: 2026-05-27 09:17 Last updated: 2026-06-06 13:04
#algorithm #Dijkstra #SPFA

Core Logic and Mathematical Principles

The essence of the Single Source Shortest Path (SSSP) problem is to find the minimum edge weight path from a specific source point $s$ to all other nodes $v \in V$ in a weighted graph $G=(V, E)$. Under the NOIP system, the Dijkstra heap optimization algorithm and the SPFA algorithm represent two distinctly different topological approximation paradigms.

1. Greedy Paradigm: Dijkstra's Algorithm

The core of Dijkstra's algorithm is a greedy expansion based on the topological blue and white point sets.

2. Dynamic Approximation Paradigm: SPFA Algorithm

SPFA (Shortest Path Faster Algorithm) is essentially the Bellman-Ford algorithm optimized with a queue, belonging to the iterative approximation of dynamic programming.

Algorithm Derivation and State Design

Define $dist[u]$ as the current shortest path estimate from the source point $s$ to node $u$.

1. Triangle Inequality and Relaxation Operation

For any edge $(u, v) \in E$ with weight $w$, the relaxation operation is the core state transition equation of the entire shortest path algorithm:

$$dist[v] = \min(dist[v], dist[u] + w)$$

Physical Meaning: It checks whether the path from $s$ to $v$ via $u$ is shorter than the currently known direct path or the path to $v$ through other means.

2. Dijkstra Heap Optimization State Design

The state stored in the priority queue is a pair $(d, u)$, where $u$ is the node index and $d$ is the current $dist[u]$. The top element of the binary heap satisfies:

$$u_{\text{next}} = \arg\min_{v \in T} (dist[v])$$

Since the default of C++ std::priority_queue is a max heap, the comparison operator of the structure must be overloaded to transform it into a min heap during implementation.

C++ Standard Source Code (Dijkstra Heap Optimization Standard Industrial Template)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

const long long INF = 0x3f3f3f3f3f3f3f3fLL; // Use a sufficiently large long integer to prevent overflow
const int MAXN = 100005;

struct Edge {
    int to;
    long long weight;
};

struct HeapNode {
    long long d;
    int u;
    // Critical low-level error prevention: must strictly implement min-heap comparison, otherwise max-heap will cause complexity degradation to brute-force
    bool operator>(const HeapNode& rhs) const {
        return d > rhs.d;
    }
};

std::vector<Edge> adj[MAXN];
long long dist[MAXN];
bool vis[MAXN]; // Mark whether it has been added to the set S

void dijkstra(int s, int n) {
    // State initialization
    for (int i = 1; i <= n; ++i) {
        dist[i] = INF;
        vis[i] = false;
    }

    // Declare min-heap
    std::priority_queue<HeapNode, std::vector<HeapNode>, std::greater<HeapNode> > pq;

dist[s] = 0;
    pq.push(HeapNode{0, s});

    while (!pq.empty()) {
        HeapNode current = pq.top();
        pq.pop();

        int u = current.u;

        // Key pitfall: there may be old, longer distance redundant nodes in the heap, must skip them
        if (vis[u]) continue; 
        vis[u] = true; // Officially included in the set S

        for (size_t i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].to;
            long long w = adj[u][i].weight;

            // Triangle inequality state transition
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push(HeapNode{dist[v], v});
            }
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m, s;
    if (!(std::cin >> n >> m >> s)) return 0;

    for (int i = 0; i < m; ++i) {
        int u, v;
        long long w;
        std::cin >> u >> v >> w;
        adj[u].push_back(Edge{v, w}); // If it's an undirected graph, need to push_back in both directions
    }

    dijkstra(s, n);

    for (int i = 1; i <= n; ++i) {
        if (dist[i] == INF) {
            std::cout << 2147483647 << " "; // Corresponds to the unreachable output value required by some problems
        } else {
            std::cout << dist[i] << " ";
        }
    }
    std::cout << "\n";

    return 0;
}

NOIP Practical Avoidance Guide

  1. Blindly trusting SPFA leading to being trapped in competitions: Some contestants, due to the habit of the concise SPFA code or the desire for its ability to handle negative weights, blindly choose SPFA for routine problems without any negative weight edges. In recent NOIP/provincial evaluations, for any non-negative single-source shortest path problem, the problem setter will definitely construct special malicious data to trap SPFA. Once SPFA is chosen, it is equivalent to betting $O((V+E)\log V$) against the worst-case scenario of $O(VE)$, directly leading to TLE and losing over 60% of the score. When there are no negative weight edges, only Dijkstra heap optimization can be used.
  2. Missing if (vis[u]) continue; in heap optimization leading to time explosion: Linear relaxation operations can cause the same node $u$ to be updated multiple times and repeatedly pushed into the priority queue. If the lazy deletion check if (vis[u]) continue; is not done, when facing dense graphs, the dequeued nodes will carry a lot of outdated dirty data and re-execute the for loop to traverse the outgoing edges, which can cause the actual size of the priority queue to balloon to $O(E)$, leading to a direct degradation of the algorithm's time complexity, failing to achieve the expected logarithmic optimization effect.

Classic NOIP/Luogu Problems

1. Luogu P4779 [Template] Single Source Shortest Path (Standard Version)

2. Luogu P3003 [USACO10MAR] Grass Traveling G

Original Source: local://10.1
[h] Back to Home
© 2026 Nefut. | About Us | Contact Us | Privacy Policy | RSS