dijkstra算法路径规划代码

Dijkstra算法是一种常用的最短路径算法，其输入为有向图和源点，输出为从源点到其他所有点的最短路径。

首先，需要定义一个用于存储图信息的数据结构，其中包括点集、边集、边权值等信息。其次，需要定义一个数组d用于存储源点到各个点的当前最短距离，以及一个数组vis用于标记该点是否已经被加入到最短路径中。初始时，d数组赋值为无穷大，vis数组赋值为false。

接下来，从源点开始，将其加入到最短路径中，更新源点到其他点的最短距离，然后再从未加入到最短路径中的点中选取距离源点最近的点作为下一个加入到最短路径中的点，重复上述操作，直到所有的点都被加入到最短路径中为止。

具体实现代码如下：

const int INF = 0x3f3f3f3f;
const int MAXV = 1005;

struct edge {
    int to, w;
};

vector<edge> G[MAXV];
int d[MAXV];
bool vis[MAXV];

void dijkstra(int s) {
    memset(vis, false, sizeof(vis));
    memset(d, INF, sizeof(d));
    d[s] = 0;

    for (int i = 1; i <= n; i++) {
        int u = -1;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && (u == -1 || d[u] > d[j])) {
                u = j;
            }
        }
        vis[u] = true;

        for (int j = 0; j < G[u].size(); j++) {
            int v = G[u][j].to;
            int w = G[u][j].w;
            if (!vis[v] && d[v] > d[u] + w) {
                d[v] = d[u] + w;
            }
        }
    }
}

其中，s为源点，n为点的数量，G为图的邻接表表示。算法的时间复杂度为O(n^2)，可通过堆优化将其优化为O(nlogn)。