全局路径规划算法——Dij

Dijkstra算法是一种常用的全局路径规划算法，用于计算图中两个节点之间的最短路径。该算法的基本思想是通过不断更新起点到各个节点的距离来找到最短路径。

具体实现步骤如下：
1. 创建一个距离表，记录起点到各个节点的当前最短距离，默认将起点到自身的距离设为0，其他节点设为无穷大。
2. 创建一个已访问节点的集合，初始时只包含起点。
3. 从未访问的节点中选择距离起点最近的节点，并将其加入已访问节点的集合。
4. 更新距离表：对于新加入的节点，遍历其所有邻居节点，如果经过当前节点到达邻居节点的路径比当前路径更短，则更新距离表中该邻居节点的最短距离。
5. 重复步骤3和步骤4，直到所有节点都加入了已访问节点的集合，或者找到了目标节点。

最终，通过查看距离表，可以得到起点到目标节点的最短路径以及对应的总距离。

需要注意的是，Dijkstra算法适用于没有负权边的图，对于有负权边的情况，可以使用其他算法如Bellman-Ford算法或者A*算法。此外，Dijkstra算法的时间复杂度为O(V^2)，其中V为节点数，对于较大的图来说，可能会存在效率问题。

相关问题

数据结构知识，读入一个有向图带权的邻接矩阵，图最短路径DIJ算法，用c语言实现。

好的，我可以帮您回答这个问题。

首先，我们需要了解一下 Dijkstra 算法。Dijkstra 算法用于解决带权有向图中单源最短路径问题，即从一个源点出发，到其他所有点的最短路径。

算法步骤如下：

1. 初始化：将源点加入已访问集合，其余点加入未访问集合，并将源点到各个点的距离初始化为无穷大。

2. 选取距离最短的点：从未访问集合中选取距离源点最近的点，并将其加入已访问集合。

3. 更新距离：更新源点到未访问集合中的点的距离。如果通过当前已访问的点到达该点的距离比源点直接到该点的距离更短，则更新该点的距离。

4. 重复执行第2步和第3步，直到所有点都被加入已访问集合。

现在，我们来看一下使用 C 语言实现 Dijkstra 算法的代码：

#include <stdio.h>
#define MAX 100         // 定义最大顶点数
#define INF 0x3f3f3f3f  // 定义无穷大

int graph[MAX][MAX];    // 有向图的邻接矩阵
int dist[MAX];          // 存储源点到各个顶点的最短距离
int visited[MAX];       // 标记顶点是否已经访问

void Dijkstra(int start, int n)
{
    // 初始化
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
        dist[i] = graph[start][i];
    }
    visited[start] = 1;
    dist[start] = 0;

    // 进行 n-1 次迭代
    for (int i = 0; i < n-1; i++) {
        int min_dist = INF;
        int min_index = -1;
        // 选取距离最短的点
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                min_index = j;
            }
        }
        if (min_index == -1) {
            break;
        }
        visited[min_index] = 1;
        // 更新距离
        for (int j = 0; j < n; j++) {
            if (!visited[j] && graph[min_index][j] != INF && dist[min_index] + graph[min_index][j] < dist[j]) {
                dist[j] = dist[min_index] + graph[min_index][j];
            }
        }
    }
}

int main()
{
    int n, start;
    printf("请输入顶点数：");
    scanf("%d", &n);
    printf("请输入邻接矩阵：\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
            if (graph[i][j] == -1) {
                graph[i][j] = INF;
            }
        }
    }
    printf("请输入起点编号：");
    scanf("%d", &start);
    Dijkstra(start, n);
    printf("源点到各个顶点的最短距离为：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", dist[i]);
    }
    printf("\n");
    return 0;
}

在这个代码中，我们输入了有向图的邻接矩阵，并将 -1 视为无穷大。然后，我们输入起点编号，调用 Dijkstra 函数计算源点到各个顶点的最短距离，最后输出结果。

希望能对您有所帮助！