Dijkstra算法：单源最短路径的最优解

算法原理

Dijkstra算法是由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年提出的图算法，用于计算加权图中单个源点到所有其他顶点的最短路径。该算法采用贪心策略，每次选择当前距离最短的未访问顶点，并更新其邻居的距离。

基本思想

1. 初始化：设置源点距离为0，其他所有顶点距离为无穷大
2. 选择最近顶点：从未访问的顶点中选择距离最小的顶点
3. 松弛操作：更新该顶点所有邻居的最短距离
4. 标记已访问：将当前顶点标记为已访问
5. 重复过程：重复步骤2-4，直到所有顶点都被访问

松弛操作

松弛是Dijkstra算法的核心操作：

if (dist[u] + weight(u,v) < dist[v]) {
    dist[v] = dist[u] + weight(u,v);
    predecessor[v] = u;
}

优缺点分析

优点

1. 最优性保证：对于非负权重图，保证找到最短路径
2. 时间复杂度较好：使用优先队列时为O((V+E)log V)
3. 实用性强：在实际应用中表现优秀
4. 可扩展性好：容易修改以适应不同需求

缺点

1. 不支持负权边：算法假设所有边权重非负
2. 空间复杂度较高：需要额外存储距离和前驱信息
3. 不适合动态图：图结构变化时需要重新计算
4. 单源限制：每次只能计算一个源点的最短路径

使用场景

适用场景

1. GPS导航系统：计算最短路径或最快路径
2. 网络路由：在计算机网络中寻找最优路由
3. 游戏开发：AI角色的路径规划
4. 社交网络分析：计算影响力传播路径
5. 物流优化：配送路线规划
6. 电路设计：最短连线问题

不适用场景

1. 存在负权边：应使用Bellman-Ford算法
2. 需要所有顶点对最短路径：应使用Floyd-Warshall算法
3. 动态变化的图：需要支持动态更新的算法

C语言实现

基础版本实现

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#include <string.h>

#define MAX_VERTICES 100
#define INF INT_MAX

// 邻接表节点
typedef struct AdjListNode {
    int dest;
    int weight;
    struct AdjListNode* next;
} AdjListNode;

// 邻接表
typedef struct AdjList {
    AdjListNode* head;
} AdjList;

// 图结构
typedef struct Graph {
    int vertices;
    AdjList* array;
} Graph;

// 优先队列节点（用于优化版本）
typedef struct MinHeapNode {
    int vertex;
    int distance;
} MinHeapNode;

// 最小堆结构
typedef struct MinHeap {
    int size;
    int capacity;
    int* pos;        // 顶点在堆中的位置
    MinHeapNode** array;
} MinHeap;

// 图操作函数
AdjListNode* create_adj_list_node(int dest, int weight) {
    AdjListNode* new_node = (AdjListNode*)malloc(sizeof(AdjListNode));
    new_node->dest = dest;
    new_node->weight = weight;
    new_node->next = NULL;
    return new_node;
}

Graph* create_graph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->vertices = vertices;
    graph->array = (AdjList*)malloc(vertices * sizeof(AdjList));
    
    for (int i = 0; i < vertices; i++) {
        graph->array[i].head = NULL;
    }
    
    return graph;
}

void add_edge(Graph* graph, int src, int dest, int weight) {
    AdjListNode* new_node = create_adj_list_node(dest, weight);
    new_node->next = graph->array[src].head;
    graph->array[src].head = new_node;
}

/**
 * 简单版本的Dijkstra算法（使用数组查找最小值）
 * 时间复杂度：O(V²)
 */
void dijkstra_simple(Graph* graph, int src) {
    int V = graph->vertices;
    int* dist = (int*)malloc(V * sizeof(int));      // 距离数组
    bool* visited = (bool*)calloc(V, sizeof(bool)); // 访问标记
    int* parent = (int*)malloc(V * sizeof(int));    // 前驱数组
    
    // 初始化距离数组
    for (int i = 0; i < V; i++) {
        dist[i] = INF;
        parent[i] = -1;
    }
    dist[src] = 0;
    
    // 主循环
    for (int count = 0; count < V - 1; count++) {
        // 找到未访问顶点中距离最小的顶点
        int min_dist = INF;
        int min_index = -1;
        
        for (int v = 0; v < V; v++) {
            if (!visited[v] && dist[v] < min_dist) {
                min_dist = dist[v];
                min_index = v;
            }
        }
        
        if (min_index == -1) break; // 没有可达的顶点
        
        visited[min_index] = true;
        
        // 松弛操作：更新相邻顶点的距离
        AdjListNode* current = graph->array[min_index].head;
        while (current != NULL) {
            int v = current->dest;
            int weight = current->weight;
            
            if (!visited[v] && dist[min_index] != INF && 
                dist[min_index] + weight < dist[v]) {
                dist[v] = dist[min_index] + weight;
                parent[v] = min_index;
            }
            current = current->next;
        }
    }
    
    // 打印结果
    printf("从顶点 %d 到各顶点的最短距离:\n", src);
    for (int i = 0; i < V; i++) {
        printf("到顶点 %d: ", i);
        if (dist[i] == INF) {
            printf("无法到达\n");
        } else {
            printf("距离 %d, 路径: ", dist[i]);
            print_path(parent, i);
            printf("\n");
        }
    }
    
    free(dist);
    free(visited);
    free(parent);
}

/**
 * 打印路径
 */
void print_path(int parent[], int vertex) {
    if (parent[vertex] == -1) {
        printf("%d", vertex);
        return;
    }
    
    print_path(parent, parent[vertex]);
    printf(" -> %d", vertex);
}

// 最小堆操作函数
MinHeap* create_min_heap(int capacity) {
    MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));
    heap->pos = (int*)malloc(capacity * sizeof(int));
    heap->size = 0;
    heap->capacity = capacity;
    heap->array = (MinHeapNode**)malloc(capacity * sizeof(MinHeapNode*));
    return heap;
}

MinHeapNode* create_min_heap_node(int vertex, int distance) {
    MinHeapNode* node = (MinHeapNode*)malloc(sizeof(MinHeapNode));
    node->vertex = vertex;
    node->distance = distance;
    return node;
}

void swap_min_heap_nodes(MinHeapNode** a, MinHeapNode** b) {
    MinHeapNode* temp = *a;
    *a = *b;
    *b = temp;
}

void min_heapify(MinHeap* heap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;
    
    if (left < heap->size && 
        heap->array[left]->distance < heap->array[smallest]->distance) {
        smallest = left;
    }
    
    if (right < heap->size && 
        heap->array[right]->distance < heap->array[smallest]->distance) {
        smallest = right;
    }
    
    if (smallest != idx) {
        MinHeapNode* smallest_node = heap->array[smallest];
        MinHeapNode* idx_node = heap->array[idx];
        
        heap->pos[smallest_node->vertex] = idx;
        heap->pos[idx_node->vertex] = smallest;
        
        swap_min_heap_nodes(&heap->array[smallest], &heap->array[idx]);
        min_heapify(heap, smallest);
    }
}

bool is_empty(MinHeap* heap) {
    return heap->size == 0;
}

MinHeapNode* extract_min(MinHeap* heap) {
    if (is_empty(heap)) return NULL;
    
    MinHeapNode* root = heap->array[0];
    MinHeapNode* last_node = heap->array[heap->size - 1];
    
    heap->array[0] = last_node;
    heap->pos[root->vertex] = heap->size - 1;
    heap->pos[last_node->vertex] = 0;
    
    heap->size--;
    min_heapify(heap, 0);
    
    return root;
}

void decrease_key(MinHeap* heap, int vertex, int distance) {
    int i = heap->pos[vertex];
    heap->array[i]->distance = distance;
    
    while (i && heap->array[i]->distance < heap->array[(i - 1) / 2]->distance) {
        heap->pos[heap->array[i]->vertex] = (i - 1) / 2;
        heap->pos[heap->array[(i - 1) / 2]->vertex] = i;
        
        swap_min_heap_nodes(&heap->array[i], &heap->array[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

bool is_in_min_heap(MinHeap* heap, int vertex) {
    return heap->pos[vertex] < heap->size;
}

/**
 * 优化版本的Dijkstra算法（使用最小堆）
 * 时间复杂度：O((V+E)log V)
 */
void dijkstra_optimized(Graph* graph, int src) {
    int V = graph->vertices;
    int* dist = (int*)malloc(V * sizeof(int));
    int* parent = (int*)malloc(V * sizeof(int));
    
    MinHeap* heap = create_min_heap(V);
    
    // 初始化
    for (int v = 0; v < V; v++) {
        dist[v] = INF;
        parent[v] = -1;
        heap->array[v] = create_min_heap_node(v, dist[v]);
        heap->pos[v] = v;
    }
    
    heap->array[src] = create_min_heap_node(src, dist[src]);
    heap->pos[src] = src;
    dist[src] = 0;
    decrease_key(heap, src, dist[src]);
    heap->size = V;
    
    while (!is_empty(heap)) {
        MinHeapNode* min_heap_node = extract_min(heap);
        int u = min_heap_node->vertex;
        
        AdjListNode* current = graph->array[u].head;
        while (current != NULL) {
            int v = current->dest;
            
            if (is_in_min_heap(heap, v) && dist[u] != INF && 
                current->weight + dist[u] < dist[v]) {
                dist[v] = dist[u] + current->weight;
                parent[v] = u;
                decrease_key(heap, v, dist[v]);
            }
            current = current->next;
        }
        free(min_heap_node);
    }
    
    // 打印结果
    printf("优化版本 - 从顶点 %d 到各顶点的最短距离:\n", src);
    for (int i = 0; i < V; i++) {
        printf("到顶点 %d: ", i);
        if (dist[i] == INF) {
            printf("无法到达\n");
        } else {
            printf("距离 %d, 路径: ", dist[i]);
            print_path(parent, i);
            printf("\n");
        }
    }
    
    free(dist);
    free(parent);
    free(heap->pos);
    free(heap->array);
    free(heap);
}

/**
 * 查找特定目标的最短路径（优化：找到目标后立即停止）
 */
int dijkstra_single_target(Graph* graph, int src, int target, int path[], int* path_length) {
    int V = graph->vertices;
    int* dist = (int*)malloc(V * sizeof(int));
    bool* visited = (bool*)calloc(V, sizeof(bool));
    int* parent = (int*)malloc(V * sizeof(int));
    
    // 初始化
    for (int i = 0; i < V; i++) {
        dist[i] = INF;
        parent[i] = -1;
    }
    dist[src] = 0;
    
    for (int count = 0; count < V - 1; count++) {
        int min_dist = INF;
        int min_index = -1;
        
        for (int v = 0; v < V; v++) {
            if (!visited[v] && dist[v] < min_dist) {
                min_dist = dist[v];
                min_index = v;
            }
        }
        
        if (min_index == -1) break;
        
        visited[min_index] = true;
        
        // 如果到达目标，提前结束
        if (min_index == target) {
            break;
        }
        
        AdjListNode* current = graph->array[min_index].head;
        while (current != NULL) {
            int v = current->dest;
            int weight = current->weight;
            
            if (!visited[v] && dist[min_index] != INF && 
                dist[min_index] + weight < dist[v]) {
                dist[v] = dist[min_index] + weight;
                parent[v] = min_index;
            }
            current = current->next;
        }
    }
    
    // 构造路径
    if (dist[target] == INF) {
        free(dist);
        free(visited);
        free(parent);
        return -1; // 目标不可达
    }
    
    int temp_path[MAX_VERTICES];
    int temp_length = 0;
    int current = target;
    
    while (current != -1) {
        temp_path[temp_length++] = current;
        current = parent[current];
    }
    
    // 反转路径
    *path_length = temp_length;
    for (int i = 0; i < temp_length; i++) {
        path[i] = temp_path[temp_length - 1 - i];
    }
    
    int result = dist[target];
    free(dist);
    free(visited);
    free(parent);
    return result;
}

/**
 * A*算法的简化版本（启发式Dijkstra）
 */
int heuristic(int vertex, int target) {
    // 简单的启发式函数（实际应用中需要根据具体问题设计）
    return abs(vertex - target);
}

void dijkstra_a_star(Graph* graph, int src, int target) {
    int V = graph->vertices;
    int* dist = (int*)malloc(V * sizeof(int));
    int* f_score = (int*)malloc(V * sizeof(int)); // f = g + h
    bool* visited = (bool*)calloc(V, sizeof(bool));
    int* parent = (int*)malloc(V * sizeof(int));
    
    for (int i = 0; i < V; i++) {
        dist[i] = INF;
        f_score[i] = INF;
        parent[i] = -1;
    }
    
    dist[src] = 0;
    f_score[src] = heuristic(src, target);
    
    while (true) {
        int min_f = INF;
        int current = -1;
        
        // 选择f值最小的未访问顶点
        for (int v = 0; v < V; v++) {
            if (!visited[v] && f_score[v] < min_f) {
                min_f = f_score[v];
                current = v;
            }
        }
        
        if (current == -1 || current == target) break;
        
        visited[current] = true;
        
        AdjListNode* neighbor = graph->array[current].head;
        while (neighbor != NULL) {
            int v = neighbor->dest;
            int tentative_g = dist[current] + neighbor->weight;
            
            if (tentative_g < dist[v]) {
                dist[v] = tentative_g;
                f_score[v] = dist[v] + heuristic(v, target);
                parent[v] = current;
            }
            neighbor = neighbor->next;
        }
    }
    
    printf("A*算法结果:\n");
    if (dist[target] == INF) {
        printf("目标不可达\n");
    } else {
        printf("最短距离: %d, 路径: ", dist[target]);
        print_path(parent, target);
        printf("\n");
    }
    
    free(dist);
    free(f_score);
    free(visited);
    free(parent);
}

// 测试函数
void print_graph(Graph* graph) {
    printf("图的邻接表表示:\n");
    for (int v = 0; v < graph->vertices; v++) {
        AdjListNode* current = graph->array[v].head;
        printf("顶点 %d: ", v);
        while (current) {
            printf("-> %d(%d) ", current->dest, current->weight);
            current = current->next;
        }
        printf("\n");
    }
    printf("\n");
}

void test_dijkstra_basic() {
    printf("=== Dijkstra算法基础测试 ===\n");
    
    Graph* graph = create_graph(9);
    add_edge(graph, 0, 1, 4);
    add_edge(graph, 0, 7, 8);
    add_edge(graph, 1, 2, 8);
    add_edge(graph, 1, 7, 11);
    add_edge(graph, 2, 3, 7);
    add_edge(graph, 2, 8, 2);
    add_edge(graph, 2, 5, 4);
    add_edge(graph, 3, 4, 9);
    add_edge(graph, 3, 5, 14);
    add_edge(graph, 4, 5, 10);
    add_edge(graph, 5, 6, 2);
    add_edge(graph, 6, 7, 1);
    add_edge(graph, 6, 8, 6);
    add_edge(graph, 7, 8, 7);
    
    print_graph(graph);
    
    dijkstra_simple(graph, 0);
    printf("\n");
    dijkstra_optimized(graph, 0);
    printf("\n");
}

void test_single_target() {
    printf("=== 单目标最短路径测试 ===\n");
    
    Graph* graph = create_graph(6);
    add_edge(graph, 0, 1, 2);
    add_edge(graph, 0, 2, 4);
    add_edge(graph, 1, 2, 1);
    add_edge(graph, 1, 3, 7);
    add_edge(graph, 2, 4, 3);
    add_edge(graph, 3, 4, 2);
    add_edge(graph, 3, 5, 1);
    add_edge(graph, 4, 5, 5);
    
    int path[MAX_VERTICES];
    int path_length;
    int distance = dijkstra_single_target(graph, 0, 5, path, &path_length);
    
    printf("从顶点 0 到顶点 5:\n");
    if (distance == -1) {
        printf("目标不可达\n");
    } else {
        printf("最短距离: %d\n", distance);
        printf("路径: ");
        for (int i = 0; i < path_length; i++) {
            printf("%d", path[i]);
            if (i < path_length - 1) printf(" -> ");
        }
        printf("\n");
    }
    printf("\n");
}

void test_a_star() {
    printf("=== A*算法测试 ===\n");
    
    Graph* graph = create_graph(5);
    add_edge(graph, 0, 1, 1);
    add_edge(graph, 0, 2, 4);
    add_edge(graph, 1, 3, 2);
    add_edge(graph, 2, 3, 1);
    add_edge(graph, 3, 4, 3);
    
    dijkstra_a_star(graph, 0, 4);
    printf("\n");
}

int main() {
    test_dijkstra_basic();
    test_single_target();
    test_a_star();
    
    return 0;
}

算法变种和应用

1. 双向Dijkstra

int bidirectional_dijkstra(Graph* graph, int src, int target) {
    // 从源点和目标点同时开始搜索
    // 当两个搜索相遇时，找到最短路径
    // 可以显著减少搜索空间
    return 0; // 简化实现
}

2. 多目标Dijkstra

void dijkstra_multiple_targets(Graph* graph, int src, int targets[], int target_count) {
    // 计算到多个目标的最短路径
    // 当所有目标都找到时停止搜索
}

复杂度分析

时间复杂度

• 简单实现：O(V²) - 使用线性搜索找最小距离
• 优先队列实现：O((V+E)log V) - 使用二叉堆
• 斐波那契堆实现：O(E + V log V) - 理论最优

空间复杂度

• 距离数组：O(V)
• 前驱数组：O(V)
• 优先队列：O(V)
• 总空间复杂度：O(V)

实际应用

1. GPS导航：计算最短或最快路径
2. 网络路由：OSPF协议中的路径选择
3. 游戏AI：角色移动路径规划
4. 社交网络：最短关系链查找
5. 电路设计：最短连线布局
6. 航空调度：最优航线规划

总结

Dijkstra算法是解决单源最短路径问题的经典算法，其贪心策略和最优性保证使其在实际应用中被广泛采用。理解Dijkstra算法不仅有助于解决路径规划问题，更重要的是掌握其贪心思想和松弛操作的概念，这些思想在许多其他算法中都有应用。

通过合理的数据结构优化，Dijkstra算法可以达到很好的性能表现，是图算法学习中不可或缺的重要算法。

版权所有，如有侵权请联系我