FC09-Dijkstra算法：求有向图or无向图中从源点到其他各顶点的最短路径¶

代码实现¶

C
// Dijkstra算法：求有向图/无向图中从源点到其他各顶点的最短路径
// 参数：G - 图的邻接矩阵表示，v - 源点（起始顶点）
void Dijkstra(MGraph G, int v) {
    // visit数组：标记顶点是否已确定最短路径
    int visit[maxsize] = {0};

    // lowcost数组：存储源点到各顶点的当前最短距离
    int lowcost[G.numver];

    // parent数组：存储最短路径中各顶点的前驱节点
    int parent[G.numver];

    // 初始化lowcost和parent数组
    for (int i = 0; i < G.numver; i++) {
        lowcost[i] = INT16_MAX;  // 初始时所有顶点距离设为无穷大
        parent[i] = -1;          // 初始时所有顶点的前驱节点设为-1
    }

    // 源点到自身的距离设为0
    lowcost[v] = 0;

    // 循环G.numver-1次，每次确定一个顶点的最短路径
    for (int i = 0; i < G.numver - 1; i++) {
        // 步骤1：在未确定最短路径的顶点中找到距离最小的顶点
        int pos, min_val = INT16_MAX;
        for (int j = 0; j < G.numver; j++) {
            if (lowcost[j] < min_val && visit[j] == 0) {
                pos = j;           // 记录距离最小的顶点位置
                min_val = lowcost[j]; // 记录最小距离值
            }
        }

        // 将找到的顶点标记为已确定最短路径
        visit[pos] = 1;

        // 步骤2：更新其他顶点的最短距离
        for (int j = 0; j < G.numver; j++) {
            // 如果顶点j未确定最短路径 且 通过顶点pos到j的距离更短
            if (lowcost[j] > G.edge[pos][j] + lowcost[pos] && visit[j] == 0) {
                lowcost[j] = G.edge[pos][j] + lowcost[pos]; // 更新最短距离
                parent[j] = pos;             // 更新前驱节点
            }
        }
    }

    // 输出从源点到各顶点的最短路径和路径信息
    for (int i = 0; i < G.numver; i++) {
        // 使用栈来逆序输出路径
        int st[G.numver], top = -1, j = i;

        // 从终点开始，沿着前驱节点回溯到源点
        while (parent[j] != -1) {
            st[++top] = j;      // 将当前顶点入栈
            j = parent[j];      // 移动到前驱节点
        }

        // 输出路径：源点 -> ... -> 终点
        printf("%d ", v);       // 输出源点

        // 逆序输出栈中的顶点（即正序的路径）
        while (top != -1) {
            printf("%d ", st[top--]);
        }

        // 输出最短距离
        printf("%d ", lowcost[i]);
    }
}

代码逻辑解析¶

1. Dijkstra算法基本思想¶

从源点开始，逐步确定到各顶点的最短路径
每次选择当前距离源点最近的未确定顶点
通过该顶点更新其他顶点的最短距离
重复此过程直到所有顶点的最短路径都确定

2. 关键数据结构¶

visit数组：标记顶点是否已确定最短路径
lowcost数组：记录源点到各顶点的当前最短距离
parent数组：记录最短路径中各顶点的前驱节点（用于路径重构）

3. 算法步骤详解¶

步骤1：初始化¶

C
// 初始化所有顶点到源点的距离为无穷大
for (int i = 0; i < G.numver; i++) {
    lowcost[i] = INT16_MAX;
    parent[i] = -1;
}
lowcost[v] = 0; // 源点到自身的距离设为0

步骤2：主循环（执行n-1次）¶

C
for (int i = 0; i < G.numver - 1; i++) {
    // 选择距离最小的顶点
    // 更新其他顶点的距离
}

步骤3：选择最近顶点¶

C
int pos, min_val = INT16_MAX;
for (int j = 0; j < G.numver; j++) {
    if (lowcost[j] < min_val && visit[j] == 0) {
        pos = j;
        min_val = lowcost[j];
    }
}
visit[pos] = 1; // 标记为已确定最短路径

步骤4：更新距离¶

C
// 松弛操作：通过顶点pos更新其他顶点的距离
if (lowcost[j] > G.edge[pos][j] + lowcost[pos] && visit[j] == 0) {
    lowcost[j] = G.edge[pos][j] + lowcost[pos]; // 更新最短距离
    parent[j] = pos;             // 更新前驱节点
}

步骤5：路径输出¶

C
// 从终点沿着前驱节点回溯到源点，使用栈逆序输出
while (parent[j] != -1) {
    st[++top] = j;
    j = parent[j];
}

时间复杂度分析¶

1. 外层循环¶

执行 G.numver - 1 次，即 O(V) 次

2. 内层循环¶

找最小顶点：O(V) 时间
更新距离：O(V) 时间

3. 路径输出¶

每个顶点的路径输出：O(V) 时间
总共 V 个顶点：O(V²) 时间

4. 总体时间复杂度¶

O(V) × [O(V) + O(V)] + O(V²) = O(V²)
其中 V 是顶点数

5. 优化可能性¶

使用优先队列（最小堆）可以优化到 O((V + E) log V)
使用斐波那契堆可以优化到 O(V log V + E)

空间复杂度分析¶

1. 额外数组空间¶

visit[]：O(V)
lowcost[]：O(V)
parent[]：O(V)
st[]：O(V)

2. 局部变量¶

常量级别的额外空间

3. 总体空间复杂度¶

O(V)，其中 V 是顶点数

较难理解部分的说明¶

1. 松弛操作的理解¶

C
// 松弛操作的核心思想：
// 如果"源点→当前顶点pos→目标顶点j"的距离 < "源点→目标顶点j"的当前距离
// 则更新目标顶点j的最短距离和前驱节点

if (lowcost[j] > G.edge[pos][j] + lowcost[pos] && visit[j] == 0) {
    lowcost[j] = G.edge[pos][j] + lowcost[pos]; // 新路径更短
    parent[j] = pos; // 更新前驱节点
}

// 举例说明：
// lowcost[j] = 10 (当前已知的最短距离)
// G.edge[pos][j] = 3 (从pos到j的距离)
// lowcost[pos] = 5 (从源点到pos的最短距离)
// 则通过pos的新距离 = 3 + 5 = 8 < 10，需要更新

2. 路径重构过程¶

C
// 路径重构的关键：从终点开始，沿着前驱节点回溯到源点
// 由于是逆序的，需要使用栈来正序输出

// 举例：源点0到终点3的路径为 0→1→2→3
// parent数组：parent[1]=0, parent[2]=1, parent[3]=2
// 回溯过程：3 → 2 → 1 → 0 (前驱节点序列)
// 栈存储：[3,2,1] (0是源点，不需要入栈)
// 出栈输出：1 → 2 → 3 (正序路径)
// 最终输出：0 1 2 3 (完整路径)

3. 图解说明¶

假设有向图如下：

Text Only
1 2 3 4 5 6	`0 / \ 1 3 \ / 2 边权值：0→1=2, 0→3=6, 1→2=3, 3→2=1`

邻接矩阵表示：

Text Only
1 2 3 4 5	`0 1 2 3 0 0 2 ∞ 6 (顶点0到各顶点的距离) 1 ∞ 0 3 ∞ (顶点1到各顶点的距离) 2 ∞ ∞ 0 ∞ (顶点2到各顶点的距离) 3 ∞ ∞ 1 0 (顶点3到各顶点的距离)`

Dijkstra算法执行过程（从顶点0开始）：

Text Only

初始状态：
visit = [0,0,0,0]
lowcost = [0,2,∞,6]
parent = [-1,-1,-1,-1]

第1轮：选择顶点1(min=2)
更新：lowcost[2] = min(∞, 2+3) = 5
visit = [1,1,0,0]
lowcost = [0,2,5,6]
parent = [-1,0,1,0]

第2轮：选择顶点2(min=5)
更新：lowcost[3] = min(6, 5+∞) = 6 (无更新)
visit = [1,1,1,0]
lowcost = [0,2,5,6]
parent = [-1,0,1,0]

第3轮：选择顶点3(min=6)
visit = [1,1,1,1]
lowcost = [0,2,5,6]
parent = [-1,0,1,0]

最终结果： - 0到0：路径0，距离0 - 0到1：路径0→1，距离2 - 0到2：路径0→1→2，距离5 - 0到3：路径0→3，距离6

延伸知识点¶

1. 与Prim算法的对比¶

特性	Dijkstra算法	Prim算法
目的	单源最短路径	最小生成树
更新规则	`dist[j] > edge[pos][j] + dist[pos]`	`dist[j] > edge[pos][j]`
初始值	源点为0，其他为∞	起始点为0，其他为∞
结果	树形结构（从源点出发的最短路径树）	树形结构（连接所有顶点的最小权树）

2. 优化版本 - 使用优先队列¶

C
// 使用最小堆优化的Dijkstra算法
void DijkstraOptimized(MGraph G, int v) {
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    vector<bool> visited(G.numver, false);
    vector<int> dist(G.numver, INT_MAX);
    vector<int> parent(G.numver, -1);

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

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (visited[u]) continue;
        visited[u] = true;

        for (int i = 0; i < G.numver; i++) {
            if (G.edge[u][i] && !visited[i] && dist[u] + G.edge[u][i] < dist[i]) {
                dist[i] = dist[u] + G.edge[u][i];
                parent[i] = u;
                pq.push({dist[i], i});
            }
        }
    }
}

3. 限制条件和扩展¶

Dijkstra算法的限制：¶

不能处理负权边：贪心策略在负权边情况下不成立
适用于非负权图：所有边权必须非负

处理负权边的算法：¶

C
// Bellman-Ford算法（可处理负权边）
bool BellmanFord(MGraph G, int v) {
    vector<int> dist(G.numver, INT_MAX);
    dist[v] = 0;

    // 松弛操作执行V-1次
    for (int i = 0; i < G.numver - 1; i++) {
        for (int u = 0; u < G.numver; u++) {
            for (int w = 0; w < G.numver; w++) {
                if (G.edge[u][w] && dist[u] + G.edge[u][w] < dist[w]) {
                    dist[w] = dist[u] + G.edge[u][w];
                }
            }
        }
    }

    // 检查是否存在负权回路
    for (int u = 0; u < G.numver; u++) {
        for (int w = 0; w < G.numver; w++) {
            if (G.edge[u][w] && dist[u] + G.edge[u][w] < dist[w]) {
                return false; // 存在负权回路
            }
        }
    }

    return true;
}

4. 实际应用场景¶

导航系统：GPS路径规划，寻找最短行驶路线
网络路由：互联网数据包传输的最短路径选择
社交网络：寻找两个人之间的最短关系链
游戏开发：AI寻路算法，NPC移动路径规划
物流配送：快递配送的最优路线规划
电路设计：电子信号传输的最短延迟路径

5. 算法变体和扩展¶

C
// 所有点对最短路径 - Floyd-Warshall算法
void Floyd(MGraph G) {
    int dist[maxsize][maxsize];
    int parent[maxsize][maxsize];

    // 初始化
    for (int i = 0; i < G.numver; i++) {
        for (int j = 0; j < G.numver; j++) {
            dist[i][j] = G.edge[i][j];
            parent[i][j] = (i != j && G.edge[i][j] < INT_MAX) ? i : -1;
        }
    }

    // 动态规划求解
    for (int k = 0; k < G.numver; k++) {
        for (int i = 0; i < G.numver; i++) {
            for (int j = 0; j < G.numver; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    parent[i][j] = parent[k][j];
                }
            }
        }
    }
}

Dijkstra算法体现了贪心策略在图论中的经典应用，通过局部最优选择达到全局最优解，是计算机科学中最重要的图算法之一。其核心思想是逐步扩展已知最短路径的顶点集合，直到所有顶点的最短路径都确定为止。