迪杰斯特拉算法c 实现二维数组的最短路径求和

迪杰斯特拉(Dijkstra's Algorithm)是一种用于寻找图中两点之间最短路径的贪心算法。在二维数组（矩阵）场景下，可以将其看作是一个加权网格，每个单元格有一个成本（距离或其他权重）。下面是使用C语言实现二维数组上Dijkstra算法的基本步骤：

1. 初始化：创建一个大小为矩阵边长的优先队列，其中初始所有节点的距离设为无穷大（除了起点，设为0），并标记为未访问。

2. 起点加入：将起点（通常记为`start`）的当前位置及当前距离（0）放入队列。

3. 遍历：循环直到队列为空。每次从队列中取出当前距离最小的节点。假设取到的节点为`(x, y)`。

4. 更新邻接节点：检查`(x, y)`周围的所有相邻节点（如果它们在矩阵范围内且未访问过），计算新的总距离（原距离加上从`(start, start)`到`(x, y)`的成本），如果新距离小于已知距离，则更新该节点的值，并将其加入队列。

5. 标记为已访问：设置`(x, y)`为已访问状态。

6. 重复步骤3-5，直到队列为空或找到目标节点。

7. 最终结果：返回从起点到目标节点的最短距离，如果遍历完整个矩阵还没有找到目标节点，那么表示不存在从起点到达目标的路径。

以下是简化版的C代码示例：

#include <stdio.h>
#include <queue>
#include <limits.h>

#define ROWS 5
#define COLS 5

// 定义一个结构体来存储节点信息
typedef struct Node {
    int x, y;
    int distance;
} Node;

bool compare_nodes(Node a, Node b) {
    return a.distance < b.distance;
}

void dijkstra(int graph[ROWS][COLS], int start_row, int start_col) {
    int distances[ROWS][COLS] = {INT_MAX};
    bool visited[ROWS][COLS] = {false};

    distances[start_row][start_col] = 0;
    Node current_node = {start_row, start_col, 0};

    // 使用优先队列存放节点
    priority_queue<Node, std::vector<Node>, decltype(&compare_nodes)> pq(&compare_nodes);

    pq.push(current_node);
    
    while (!pq.empty()) {
        current_node = pq.top();
        pq.pop();

        if (visited[current_node.x][current_node.y]) continue;
        visited[current_node.x][current_node.y] = true;

        // 检查邻居
        for (int i = -1; i <= 1; ++i)
            for (int j = -1; j <= 1; ++j) {
                int newRow = current_node.x + i;
                int newCol = current_node.y + j;
                
                if (newRow >= 0 && newRow < ROWS && newCol >= 0 && newCol < COLS && !visited[newRow][newCol]) {
                    int cost = graph[newRow][newCol];
                    int total_distance = distances[current_node.x][current_node.y] + cost;
                    
                    if (total_distance < distances[newRow][newCol]) {
                        distances[newRow][newCol] = total_distance;
                        Node neighbor = {newRow, newCol, total_distance};
                        pq.push(neighbor);
                    }
                }
            }
    }

    printf("最短路径之和: %d\n", distances[ROWS - 1][COLS - 1]);
}

int main() {
    int graph[ROWS][COLS] = {{0, 1, 1, 0, 0},
                            {1, 0, 1, 1, 0},
                            {1, 1, 0, 1, 1},
                            {0, 1, 1, 0, 0},
                            {0, 0, 1, 0, 0}};
    dijkstra(graph, 0, 0);
    return 0;
}