有大佬有用数组模拟的dijkstra模板吗 是静态数组，不是动态的
有大佬有用数组模拟的dijkstra模板吗 是静态数组，不是动态的自己想脑袋要炸了
用数组模拟邻接表的模板就是这个：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1005, M = 10005;
int h, e, nex, idx = 0;
void add(int a,int b)
{
e = b;
nex = h;
h = 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;j!=-1;j=nex)
{
cout << e << "->";
}
cout << endl;
}
return 0;
}
以下是用静态数组模拟Dijkstra算法的模板代码，其中dist[ i]表示起点到i点的最短距离，vis[ i]表示i点是否已经取得最短距离：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1005;
int g; // 存储邻接矩阵
int dist; // 距离数组
bool vis; // 标记数组
int n, m, s; // 点数、边数、起点编号
void dijkstra()
{
memset(dist, 0x3f, sizeof dist); // 初始化距离数组为无穷大
dist = 0; // 起点到自身的距离为0
for (int i = 0; i < n; i++)
{
int t = -1; // 找到未取得最短距离的点中距离最小的点
for (int j = 1; j <= n; j++)
if (!vis && (t == -1 || dist > dist))
t = j;
vis = true; // 标记该点已取得最短距离
// 更新未取得最短距离的点的距离
for (int j = 1; j <= n; j++)
dist = min(dist, dist + g);
}
}
int main()
{
cin >> n >> m >> s;
memset(g, 0x3f, sizeof g); // 初始化邻接矩阵为无穷大
while (m--)
{
int a, b, c;
cin >> a >> b >> c;
g = min(g, c); // 处理重边和自环边
if (a != b) g = min(g, c);
}
dijkstra();
for (int i = 1; i <= n; i++)
cout << dist[ i] << " ";
return 0;
}
需要注意的是，为了防止数组越界，在邻接矩阵g和dist数组的大小都要开到n+1。
请注意，本回答来自GPT-3.5
如果问题已经解决，请设置最佳答案 这是一个使用数组模拟邻接表的Dijkstra算法模板。它使用静态数组来存储图的边和邻接关系。
首先，我们定义了常量N和M来表示图中的点数和边数。然后，我们定义了一个数组h来存储每个点的邻接表的头指针。数组e和nex分别用于存储边的终点和下一条边的索引。变量idx用于表示当前边的索引。
接下来，我们定义了一个add函数，用于向邻接表中添加边。在add函数中，我们将边的终点存储在数组e中，将当前点的邻接表头指针存储在数组nex中，并更新当前点的邻接表头指针。
在主函数中，我们首先初始化邻接表头指针数组h为-1，表示每个点的邻接表为空。然后，我们输入点数n和边数m。接下来，我们使用一个循环来读取每条边的起点和终点，并调用add函数将边添加到邻接表中。
最后，我们使用两个嵌套循环来遍历每个点的邻接表，并输出每个点的邻接点。我们首先输出当前点的编号，然后遍历当前点的邻接表，输出每个邻接点的编号。每个邻接点之间用箭头->分隔，每个点的邻接表输出完毕后换行。
这个模板可以用来模拟有向图或无向图的邻接表，并且可以方便地进行Dijkstra算法等图算法的实现。 以下是使用静态数组模拟的Dijkstra算法模板示例：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1005;
const int INF = 0x3f3f3f3f; // 表示无穷大
int g; // 存储图的邻接矩阵
int dist; // 存储源点到各个顶点的最短距离
bool vis; // 记录顶点是否已被访问
void Dijkstra(int n, int s) {
memset(dist, INF, sizeof(dist)); // 初始化距离为无穷大
memset(vis, false, sizeof(vis)); // 初始化所有顶点未被访问
dist = 0; // 源点到自身的距离为0
for (int i = 0; i < n; i++) {
int u = -1, minDist = INF; // u用于记录当前未访问顶点中距离最小的顶点
// 寻找距离最小的顶点
for (int j = 0; j < n; j++) {
if (!vis && dist < minDist) {
u = j;
minDist = dist;
}
}
if (u == -1) break; // 所有顶点都访问过，退出循环
vis = true; // 标记顶点u为已访问
// 更新源点到其他未访问顶点的距离
for (int v = 0; v < n; v++) {
if (!vis && g != INF) {
dist = min(dist, dist + g);
}
}
}
}
int main() {
int n, m;
cin >> n >> m; // 输入点数n和边数m
// 初始化邻接矩阵，将除对角线外的元素初始化为无穷大
memset(g, INF, sizeof(g));
for (int i = 0; i < n; i++) g = 0;
int a, b, c;
for (int i = 0; i < m; i++) {
cin >> a >> b >> c; // 输入边的起点、终点和权值
g = min(g, c); // 若存在多条边，则取最小的权值
}
int s;
cin >> s; // 输入源点s
Dijkstra(n, s);
// 输出源点到各个顶点的最短距离
for (int i = 0; i < n; i++) {
cout << "源点" << s << "到达顶点" << i << "的最短距离为：" << dist << endl;
}
return 0;
}
此模板使用静态数组来模拟Dijkstra算法，其中g数组存储图的邻接矩阵，dist数组存储源点到各个顶点的最短距离，vis数组记录顶点是否已被访问。算法的核心是通过遍历未访问的顶点，选择距离最小的顶点进行松弛操作，更新最短距离。
希望以上回答对你有帮助！如果还有其他问题，请随时提问。
球一个最佳答案谢谢啦！这对我非常重要！{:10_254:}{:10_254:}{:10_254:} 陶远航 发表于 2023-10-7 19:49
以下是用静态数组模拟Dijkstra算法的模板代码，其中dist[ i]表示起点到i点的最短距离，vis[ i]表示i点是否 ...
这是邻接矩阵啊{:10_269:}@tommyyu @zhangjinxuan @学习编程中的Ben @额外减小 等我先学完基础的图论再来看。 解一：你应该这么问，C语言写这个怎么写{:10_256:}
解二：手写 vector {:10_256:} 所以你要卡常吗
页:
[1]