djstl/迪杰斯特拉算法邻接表存储
- 图的定义：该程序定义了一个图结构
MGraph，图是通过邻接链表的方式表示的。每个顶点通过vNode结构体保存，其中包含顶点的名字（name）、附加数据（data），以及指向第一个边节点的指针（firstarc）。边的信息通过Node结构体存储，其中index表示边指向的顶点索引，next是指向下一条边的指针，distance表示边的权重（即两顶点之间的距离）。 - 图的初始化：
initG函数初始化了一个包含 8 个顶点的图。顶点分别命名为 A 到 H。然后，图的边信息使用邻接矩阵edges[8][8]进行初始化，矩阵的元素代表边的权重（如果没有边，矩阵值为no，即无穷大）。根据矩阵中的数据，程序遍历并动态地构建邻接链表。
迪杰斯特拉 算法 思路
- 问题背景：迪杰斯特拉算法用于求解图中单源点到其他所有顶点的最短路径。给定一个图
G和一个源点（如 A），目标是找出从源点到其他所有顶点的最短路径和路径长度。 -
初始化：首先，定义了一个源点
fd，并通过遍历图中的顶点名称来找出源点在数组中的索引（即顶点的编号）。接着，初始化一些辅助数组：P[maxv]：前驱节点数组，用来记录最短路径中每个节点的前驱节点。D[maxv]：距离数组，用来记录源点到每个顶点的最短距离。初始时，所有顶点的距离设置为无穷大（no），源点的距离为 0。-
final[maxv]：标记数组，用来记录哪些节点已经包含在最短路径集合中。最初，源点被标记为已确定。 3. 更新邻接信息：从源点开始，查看与源点直接相连的顶点，更新它们的最短距离和前驱节点。 4. 主循环：该算法的核心部分是一个迭代过程，循环vexnum - 1次，每次找到距离当前最短的未处理节点，并更新该节点的邻接点的最短路径。 -
每次迭代，找到一个未处理节点（即距离最小的节点）并加入最短路径集合。
- 更新与该节点相邻的所有节点的距离。如果某个节点通过当前节点可以得到更短的路径，就更新该节点的最短距离和前驱节点。 5. 终止条件：如果在某次迭代中无法找到距离最小的未处理节点，说明剩余的节点不可达，算法结束。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Node{
int index;
Node* next;
int distance;
};
struct vNode{
string name; // 顶点信息
string data;
Node* firstarc; // 第一条边
};
struct MGraph{
vNode* vArray; // 顶点数组
int vexnum, arcnum; // 顶点数和边数
};
/// //////////////////////////////////////////////////////////////
const int no = 10000; // 定义无穷
void initG(MGraph &G) {
// 设定顶点数和边数
G.vexnum = 8;
G.arcnum = 14;
// 顶点信息初始化
string names[] = {"A", "B", "C", "D", "E", "F", "G", "H"};
// 动态分配顶点数组
G.vArray = new vNode[G.vexnum];
for (int i = 0; i < G.vexnum; i++) {
G.vArray[i].name = names[i]; // 设置顶点名
G.vArray[i].firstarc = NULL; // 初始化邻接链表为空
}
// 邻接矩阵初始化：存储边信息
int edges[8][8] = {
{no, 10, 3, 5, no, no, no, no}, // A -> B(10), A -> C(3), A -> D(5)
{no, no, 2, no, 7, 4, no, no}, // B -> C(2), B -> E(7), B -> F(4)
{no, no, no, no, 1, no, 8, no}, // C -> E(1), C -> G(8)
{no, no, no, no, 6, 2, 9, no}, // D -> E(6), D -> F(2), D -> G(9)
{no, no, no, no, no, no, no, 3}, // E -> H(3)
{no, no, no, no, no, no, no, 6}, // F -> H(6)
{no, no, no, no, no, no, no, 2}, // G -> H(2)
{no, no, no, no, no, no, no, no} // H 没有出边
};
// 遍历邻接矩阵，将边添加到邻接表中
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
if (edges[i][j] != no) { // 如果有边，添加到邻接表中
Node* newNode = new Node{j, G.vArray[i].firstarc, edges[i][j]}; // 创建新边节点
G.vArray[i].firstarc = newNode; // 更新链表头指针
}
}
}
// 打印图的邻接表
for (int i = 0; i < G.vexnum; i++) {
cout << G.vArray[i].name << ": ";
Node* p = G.vArray[i].firstarc; // 获取当前顶点的邻接链表
if (p == NULL) {
cout << "(没有出边)" << endl;
} else {
while (p != NULL) {
cout << G.vArray[p->index].name << "(" << p->distance << ") ";
p = p->next;
}
cout << endl;
}
}
}
// 迪杰斯特拉算法
// 迪杰斯特拉算法
void djstl(MGraph *G, string fd) {
int obj = -1;
for (int i = 0; i < G->vexnum; i++) {
if (fd == G->vArray[i].name) {
obj = i; // 寻找目标节点下标
break;
}
}
if (obj == -1) {
cout << "未找到源点!" << endl;
return;
}
int maxv = G->vexnum;
int P[maxv]; // 前驱节点数组
int D[maxv]; // 距离数组
bool final[maxv]; // 标记节点是否已加入最短路径集合
// 初始化数组
fill(P, P + maxv, 0); // 前驱节点初始化为 -1
fill(D, D + maxv, no); // 距离数组初始化为无穷大
fill(final, final + maxv, false); // 所有节点初始化为未确定最短路径
D[obj] = 0; // 源点到源点的距离为0
final[obj] = true; // 源点加入最短路径集合
// 初始化 D 和 P 数组（邻接点的距离赋值）
Node* node = G->vArray[obj].firstarc;
while (node != NULL) {
D[node->index] = node->distance;
P[node->index] = obj;
node = node->next;
}
// 主循环，循环vexnum-1次，每次确定一个节点的最短路径
for (int i = 1; i < G->vexnum; i++) {
int j = -1;
int min = no;
// 在未确定最短路径的节点中选择距离最小的节点
for (int k = 0; k < G->vexnum; k++) {
if (!final[k] && D[k] < min) {
j = k;
min = D[k];
}
}
if (j == -1) break; // 如果找不到合适的节点，退出循环
final[j] = true; // 将顶点 j 加入已确定最短路径集合
// 更新与 j 节点相邻的节点的最短路径
node = G->vArray[j].firstarc;
while (node != NULL) {
int jk = D[j] + node->distance; // 计算经过节点 j 到相邻节点的路径长度
if (!final[node->index] && jk < D[node->index]) { // 如果更短，更新路径和前驱节点
D[node->index] = jk;
P[node->index] = j;
}
node = node->next;
}
}
// 输出最短路径结果
for (int i = 0; i < G->vexnum; i++) {
if (D[i] == no) {
cout << "无法到达 " << G->vArray[i].name << endl;
} else {
cout << "最短路径到 " << G->vArray[i].name << " : 路径长度 = " << D[i] << endl;
int pre = P[i];
cout << G->vArray[i].name;
while (pre != -1) {
cout << "<-" << G->vArray[pre].name;
pre = P[pre];
}
cout << endl;
}
}
}
int main() {
// 创建图
MGraph G;
initG(G);
djstl(&G, "A");
return 0;
}