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

Mike_python小

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

自己想脑袋要炸了

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

1. 
   
2. #include <iostream>
   
3. #include <cstring>
   
4. 
   
5. using namespace std;
   
6. 
   
7. const int N = 1005, M = 10005;
   
8. 
   
9. int h[N], e[M], nex[M], idx = 0;
   
10. 
    
11. void add(int a,int b)
    
12. {
    
13.         e[idx] = b;
    
14.         nex[idx] = h[a];
    
15.         h[a] = idx;
    
16.         idx++;
    
17.        
    
18.        
    
19. }
    
20. 
    
21. 
    
22. int main()
    
23. {
    
24.         int n, m;
    
25.         int a, b;
    
26.         memset(h, -1, sizeof(h)); // 初始化
    
27.        
    
28.         cin >> n >> m; // 输入点数，边数
    
29.         for (int i=1;i<=m;i++)
    
30.         {
    
31.                 cin >> a >> b;
    
32.                 add(a, b);
    
33.                 add(b, a);
    
34.                
    
35.         }
    
36.        
    
37.         for (int i=1;i<=n;i++)
    
38.         {
    
39.                 cout << i << "->";
    
40.                 for (int j=h[i];j!=-1;j=nex[j])
    
41.                 {
    
42.                        
    
43.                         cout << e[j] << "->";
    
44.                 }
    
45.                 cout << endl;
    
46.         }
    
47.        
    
48.        
    
49.        
    
50.         return 0;
    
51. }
    

复制代码

陶远航

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

1. #include <iostream>
   
2. #include <cstring>
   
3. using namespace std;
   
4. 
   
5. const int N = 1005;
   
6. int g[N][N]; // 存储邻接矩阵
   
7. int dist[N]; // 距离数组
   
8. bool vis[N]; // 标记数组
   
9. 
   
10. int n, m, s; // 点数、边数、起点编号
    
11. 
    
12. void dijkstra()
    
13. {
    
14.     memset(dist, 0x3f, sizeof dist); // 初始化距离数组为无穷大
    
15.     dist[s] = 0; // 起点到自身的距离为0
    
16. 
    
17.     for (int i = 0; i < n; i++)
    
18.     {
    
19.         int t = -1; // 找到未取得最短距离的点中距离最小的点
    
20.         for (int j = 1; j <= n; j++)
    
21.             if (!vis[j] && (t == -1 || dist[t] > dist[j]))
    
22.                 t = j;
    
23. 
    
24.         vis[t] = true; // 标记该点已取得最短距离
    
25. 
    
26.         // 更新未取得最短距离的点的距离
    
27.         for (int j = 1; j <= n; j++)
    
28.             dist[j] = min(dist[j], dist[t] + g[t][j]);
    
29.     }
    
30. }
    
31. 
    
32. int main()
    
33. {
    
34.     cin >> n >> m >> s;
    
35. 
    
36.     memset(g, 0x3f, sizeof g); // 初始化邻接矩阵为无穷大
    
37.     while (m--)
    
38.     {
    
39.         int a, b, c;
    
40.         cin >> a >> b >> c;
    
41.         g[a][b] = min(g[a][b], c); // 处理重边和自环边
    
42.         if (a != b) g[b][a] = min(g[b][a], c);
    
43.     }
    
44. 
    
45.     dijkstra();
    
46. 
    
47.     for (int i = 1; i <= n; i++)
    
48.         cout << dist[ i] << " ";
    
49. 
    
50.     return 0;
    
51. }
    

复制代码

需要注意的是，为了防止数组越界，在邻接矩阵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算法模板示例：

2. #include <iostream>
3. #include <cstring>
4. using namespace std;
6. const int N = 1005;
7. const int INF = 0x3f3f3f3f; // 表示无穷大
8. int g[N][N]; // 存储图的邻接矩阵
9. int dist[N]; // 存储源点到各个顶点的最短距离
10. bool vis[N]; // 记录顶点是否已被访问
12. void Dijkstra(int n, int s) {
13.     memset(dist, INF, sizeof(dist)); // 初始化距离为无穷大
14.     memset(vis, false, sizeof(vis)); // 初始化所有顶点未被访问
15.     dist[s] = 0; // 源点到自身的距离为0
17.     for (int i = 0; i < n; i++) {
18.         int u = -1, minDist = INF; // u用于记录当前未访问顶点中距离最小的顶点
20.         // 寻找距离最小的顶点
21.         for (int j = 0; j < n; j++) {
22.             if (!vis[j] && dist[j] < minDist) {
23.                 u = j;
24.                 minDist = dist[j];
25.             }
26.         }
28.         if (u == -1) break; // 所有顶点都访问过，退出循环
30.         vis[u] = true; // 标记顶点u为已访问
32.         // 更新源点到其他未访问顶点的距离
33.         for (int v = 0; v < n; v++) {
34.             if (!vis[v] && g[u][v] != INF) {
35.                 dist[v] = min(dist[v], dist[u] + g[u][v]);
36.             }
37.         }
38.     }
39. }
41. int main() {
42.     int n, m;
43.     cin >> n >> m; // 输入点数n和边数m
45.     // 初始化邻接矩阵，将除对角线外的元素初始化为无穷大
46.     memset(g, INF, sizeof(g));
47.     for (int i = 0; i < n; i++) g[i][i] = 0;
49.     int a, b, c;
50.     for (int i = 0; i < m; i++) {
51.         cin >> a >> b >> c; // 输入边的起点、终点和权值
52.         g[a][b] = min(g[a][b], c); // 若存在多条边，则取最小的权值
53.     }
55.     int s;
56.     cin >> s; // 输入源点s
58.     Dijkstra(n, s);
60.     // 输出源点到各个顶点的最短距离
61.     for (int i = 0; i < n; i++) {
62.         cout << "源点" << s << "到达顶点" << i << "的最短距离为：" << dist[i] << endl;
63.     }
65.     return 0;
66. }

复制代码

此模板使用静态数组来模拟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

所以你要卡常吗