有大佬有用数组模拟的dijkstra模板吗 是静态数组，不是动态的

Mike_python小

有大佬有用数组模拟的dijkstra模板吗 是静态数组，不是动态的

自己想脑袋要炸了

用数组模拟邻接表的模板就是这个：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1005, M = 10005;

int h[N], e[M], nex[M], idx = 0;

void add(int a,int b)
{
        e[idx] = b;
        nex[idx] = h[a];
        h[a] = idx;
        idx++;
        
        
}


int main()
{
        int n, m;
        int a, b;
        memset(h, -1, sizeof(h)); // 初始化 
        
        cin >> n >> m; // 输入点数，边数 
        for (int i=1;i<=m;i++)
        {
                cin >> a >> b;
                add(a, b);
                add(b, a);
                
        }
        
        for (int i=1;i<=n;i++)
        {
                cout << i << "->";
                for (int j=h[i];j!=-1;j=nex[j])
                {
                        
                        cout << e[j] << "->";
                }
                cout << endl;
        }
        
        
        
        return 0;
}

陶远航

以下是用静态数组模拟Dijkstra算法的模板代码，其中dist[ i]表示起点到i点的最短距离，vis[ i]表示i点是否已经取得最短距离：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1005;
int g[N][N]; // 存储邻接矩阵
int dist[N]; // 距离数组
bool vis[N]; // 标记数组

int n, m, s; // 点数、边数、起点编号

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist); // 初始化距离数组为无穷大
    dist[s] = 0; // 起点到自身的距离为0

    for (int i = 0; i < n; i++)
    {
        int t = -1; // 找到未取得最短距离的点中距离最小的点
        for (int j = 1; j <= n; j++)
            if (!vis[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        vis[t] = true; // 标记该点已取得最短距离

        // 更新未取得最短距离的点的距离
        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
}

int main()
{
    cin >> n >> m >> s;

    memset(g, 0x3f, sizeof g); // 初始化邻接矩阵为无穷大
    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c); // 处理重边和自环边
        if (a != b) g[b][a] = min(g[b][a], c);
    }

    dijkstra();

    for (int i = 1; i <= n; i++)
        cout << dist[ i] << " ";

    return 0;
}

需要注意的是，为了防止数组越界，在邻接矩阵g和dist数组的大小都要开到n+1。
请注意，本回答来自GPT-3.5
如果问题已经解决，请设置最佳答案

isdkz

这是一个使用数组模拟邻接表的Dijkstra算法模板。它使用静态数组来存储图的边和邻接关系。

首先，我们定义了常量N和M来表示图中的点数和边数。然后，我们定义了一个数组h来存储每个点的邻接表的头指针。数组e和nex分别用于存储边的终点和下一条边的索引。变量idx用于表示当前边的索引。

接下来，我们定义了一个add函数，用于向邻接表中添加边。在add函数中，我们将边的终点存储在数组e中，将当前点的邻接表头指针存储在数组nex中，并更新当前点的邻接表头指针。

在主函数中，我们首先初始化邻接表头指针数组h为-1，表示每个点的邻接表为空。然后，我们输入点数n和边数m。接下来，我们使用一个循环来读取每条边的起点和终点，并调用add函数将边添加到邻接表中。

最后，我们使用两个嵌套循环来遍历每个点的邻接表，并输出每个点的邻接点。我们首先输出当前点的编号，然后遍历当前点的邻接表，输出每个邻接点的编号。每个邻接点之间用箭头->分隔，每个点的邻接表输出完毕后换行。

这个模板可以用来模拟有向图或无向图的邻接表，并且可以方便地进行Dijkstra算法等图算法的实现。

Mike_python小

以下是使用静态数组模拟的Dijkstra算法模板示例：

#include <iostream>#include <cstring>using namespace std;const int N = 1005;const int INF = 0x3f3f3f3f; // 表示无穷大int g[N][N]; // 存储图的邻接矩阵int dist[N]; // 存储源点到各个顶点的最短距离bool vis[N]; // 记录顶点是否已被访问void Dijkstra(int n, int s) {    memset(dist, INF, sizeof(dist)); // 初始化距离为无穷大    memset(vis, false, sizeof(vis)); // 初始化所有顶点未被访问    dist[s] = 0; // 源点到自身的距离为0    for (int i = 0; i < n; i++) {        int u = -1, minDist = INF; // u用于记录当前未访问顶点中距离最小的顶点        // 寻找距离最小的顶点        for (int j = 0; j < n; j++) {            if (!vis[j] && dist[j] < minDist) {                u = j;                minDist = dist[j];            }        }        if (u == -1) break; // 所有顶点都访问过，退出循环        vis[u] = true; // 标记顶点u为已访问        // 更新源点到其他未访问顶点的距离        for (int v = 0; v < n; v++) {            if (!vis[v] && g[u][v] != INF) {                dist[v] = min(dist[v], dist[u] + g[u][v]);            }        }    }}int main() {    int n, m;    cin >> n >> m; // 输入点数n和边数m    // 初始化邻接矩阵，将除对角线外的元素初始化为无穷大    memset(g, INF, sizeof(g));    for (int i = 0; i < n; i++) g[i][i] = 0;    int a, b, c;    for (int i = 0; i < m; i++) {        cin >> a >> b >> c; // 输入边的起点、终点和权值        g[a][b] = min(g[a][b], c); // 若存在多条边，则取最小的权值    }    int s;    cin >> s; // 输入源点s    Dijkstra(n, s);    // 输出源点到各个顶点的最短距离    for (int i = 0; i < n; i++) {        cout << "源点" << s << "到达顶点" << i << "的最短距离为：" << dist[i] << endl;    }    return 0;}

此模板使用静态数组来模拟Dijkstra算法，其中g数组存储图的邻接矩阵，dist数组存储源点到各个顶点的最短距离，vis数组记录顶点是否已被访问。算法的核心是通过遍历未访问的顶点，选择距离最小的顶点进行松弛操作，更新最短距离。

希望以上回答对你有帮助！如果还有其他问题，请随时提问。

球一个最佳答案谢谢啦！这对我非常重要！

Mike_python小

陶远航 发表于 2023-10-7 19:49
以下是用静态数组模拟Dijkstra算法的模板代码，其中dist[ i]表示起点到i点的最短距离，vis[ i]表示i点是否 ...

这是邻接矩阵啊@tommyyu @zhangjinxuan @学习编程中的Ben @额外减小

额外减小

等我先学完基础的图论再来看。

zhangjinxuan

解一：你应该这么问，C语言写这个怎么写

解二：手写 vector

zhangjinxuan

所以你要卡常吗