31101：Dijkstra 单源最短路

题目

在非负权有向图上，使用邻接表和最小堆求单源最短距离。不可达顶点用 UINT64_MAX 表示。

解析

堆中允许出现同一顶点的多个距离条目。弹出条目时，若其距离不是当前 distance[vertex]，它就是过期条目，直接跳过。非负边权保证已经弹出的当前最小距离不会再被更短路径改写；若允许负权，这个结论失效。

答案

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    size_t from;
    size_t to;
    uint64_t weight;
} WeightedEdge;

typedef struct WEdge WEdge;
struct WEdge {
    size_t to;
    uint64_t weight;
    WEdge *next;
};

typedef struct {
    WEdge *head;
} WAdjacency;

typedef struct {
    uint64_t distance;
    size_t vertex;
} DistanceEntry;

static bool entry_less(DistanceEntry left, DistanceEntry right) {
    if (left.distance != right.distance) {
        return left.distance < right.distance;
    }
    return left.vertex < right.vertex;
}

static void swap_entry(DistanceEntry *left, DistanceEntry *right) {
    DistanceEntry temporary = *left;
    *left = *right;
    *right = temporary;
}

static void heap_down(
    DistanceEntry *heap,
    size_t size,
    size_t index
) {
    for (;;) {
        size_t smallest = index;
        if (index < size / 2) {
            size_t left = index * 2 + 1;
            size_t right = left + 1;
            if (entry_less(heap[left], heap[smallest])) {
                smallest = left;
            }
            if (right < size &&
                entry_less(heap[right], heap[smallest])) {
                smallest = right;
            }
        }
        if (smallest == index) {
            return;
        }
        swap_entry(&heap[index], &heap[smallest]);
        index = smallest;
    }
}

static bool heap_push(
    DistanceEntry **heap,
    size_t *size,
    size_t *capacity,
    DistanceEntry entry
) {
    if (*size == *capacity) {
        size_t next = *capacity == 0 ? 8 : *capacity;
        if (next > SIZE_MAX / 2) {
            next = SIZE_MAX;
        } else {
            next *= 2;
        }
        if (next <= *size || next > SIZE_MAX / sizeof **heap) {
            return false;
        }
        DistanceEntry *replacement = realloc(
            *heap, next * sizeof **heap
        );
        if (replacement == NULL) {
            return false;
        }
        *heap = replacement;
        *capacity = next;
    }
    size_t index = (*size)++;
    (*heap)[index] = entry;
    while (index > 0) {
        size_t parent = (index - 1) / 2;
        if (!entry_less((*heap)[index], (*heap)[parent])) {
            break;
        }
        swap_entry(&(*heap)[index], &(*heap)[parent]);
        index = parent;
    }
    return true;
}

static DistanceEntry heap_pop(
    DistanceEntry *heap,
    size_t *size
) {
    DistanceEntry result = heap[0];
    --*size;
    if (*size > 0) {
        heap[0] = heap[*size];
        heap_down(heap, *size, 0);
    }
    return result;
}

static void free_adjacency(
    WAdjacency *adj,
    size_t vertex_count
) {
    if (adj == NULL) {
        return;
    }
    for (size_t i = 0; i < vertex_count; ++i) {
        WEdge *edge = adj[i].head;
        while (edge != NULL) {
            WEdge *next = edge->next;
            free(edge);
            edge = next;
        }
    }
    free(adj);
}

bool dijkstra_distances(
    size_t vertex_count,
    const WeightedEdge *edges,
    size_t edge_count,
    size_t source,
    uint64_t *out_distances
) {
    if (vertex_count == 0 || source >= vertex_count ||
        out_distances == NULL ||
        (edge_count > 0 && edges == NULL) ||
        vertex_count > SIZE_MAX / sizeof(uint64_t) ||
        vertex_count > SIZE_MAX / sizeof(WAdjacency)) {
        return false;
    }
    for (size_t i = 0; i < edge_count; ++i) {
        if (edges[i].from >= vertex_count ||
            edges[i].to >= vertex_count) {
            return false;
        }
    }
    WAdjacency *adj = calloc(vertex_count, sizeof *adj);
    uint64_t *distance = malloc(vertex_count * sizeof *distance);
    if (adj == NULL || distance == NULL) {
        free_adjacency(adj, vertex_count);
        free(distance);
        return false;
    }
    for (size_t i = 0; i < vertex_count; ++i) {
        distance[i] = UINT64_MAX;
    }
    for (size_t i = 0; i < edge_count; ++i) {
        WEdge *edge = malloc(sizeof *edge);
        if (edge == NULL) {
            free_adjacency(adj, vertex_count);
            free(distance);
            return false;
        }
        edge->to = edges[i].to;
        edge->weight = edges[i].weight;
        edge->next = adj[edges[i].from].head;
        adj[edges[i].from].head = edge;
    }

    DistanceEntry *heap = NULL;
    size_t heap_size = 0;
    size_t heap_capacity = 0;
    distance[source] = 0;
    if (!heap_push(
            &heap, &heap_size, &heap_capacity,
            (DistanceEntry){0, source}
        )) {
        free(heap);
        free_adjacency(adj, vertex_count);
        free(distance);
        return false;
    }

    bool valid = true;
    while (heap_size > 0 && valid) {
        DistanceEntry current = heap_pop(heap, &heap_size);
        if (current.distance != distance[current.vertex]) {
            continue;
        }
        for (WEdge *edge = adj[current.vertex].head;
             edge != NULL;
             edge = edge->next) {
            if (current.distance > UINT64_MAX - edge->weight) {
                valid = false;
                break;
            }
            uint64_t candidate = current.distance + edge->weight;
            if (candidate < distance[edge->to]) {
                distance[edge->to] = candidate;
                if (!heap_push(
                        &heap, &heap_size, &heap_capacity,
                        (DistanceEntry){candidate, edge->to}
                    )) {
                    valid = false;
                    break;
                }
            }
        }
    }
    if (valid) {
        memcpy(
            out_distances,
            distance,
            vertex_count * sizeof *out_distances
        );
    }
    free(heap);
    free_adjacency(adj, vertex_count);
    free(distance);
    return valid;
}

邻接表构建为 $O(V+E)$，每条边至多导致一次有效松弛，使用过期条目时总复杂度为 $O((V+E)\log V)$，额外空间为 $O(V+E)$。