关于dijkstra的一点思考

dijkstra采用邻接表存储，其中

1. e表示对于添加顺序idx的编号的节点（也可以理解为第idx+1次添加的边），其出度节点的序号是e[idx]。
2. ne[idx]表示添加顺序为idx的编号，其入度节点的上一次添加边的编号为ne[idx]，即同入度节点的上一个条的边的出度节点。例如添加 1 2 9,1 3 10两条边，那么e=[2,3],ne=[-1,0],w=[9,10],h=[0,1]。可以理解为ne记录了过去信息，h则理解为当前版本的入度节点编号
3. h[idx]表示添加顺序为idx，与之同入度节点的上一条边的编号。可以理解为ne是在这条链表中倒序访问的工具

对于i=ne[i]的理解

i=h[ver]则为获取节点序号为ver的最新添加的边的编号，而i=ne[i]则进行逆序的迭代，获取对于添加顺序的编号为i的同入度节点的上一条边的添加编号。

理解的验证

如图，构造一批数据，并用以下代码输出信息，包括入度节点，出度节点，距离，添加该边的编号。

for(int i=1;i<=n;i++){
        for(int j=h[i];j!=-1;j=ne[j]){
            int k=e[j];
            cout<<setw(2)<<i<<"--"<<setw(2)<<k<<" :"<<setw(2)<<w[j]<<"  add index:"<<j<<endl;
        }
    }

结果如下，例如，对于 $1$ 号序号节点，顺序添加的边的出度节点分别是 $3,2,4$，其输出却是倒序输出的，与理解相符。对于其他节点均符合。

chatgpt4.0评价与修正

你的理解基本是正确的，但在一些细节上可以更加明确。以下是对你理解的确认和一些补充说明：

1. 关于 e 和 w

• e[idx] 表示边的目的节点（即边的终点）。
• w[idx] 表示边的权重。

2. 关于 ne

• ne[idx] 表示编号为 idx 的边的上一条边在链表中的编号。这个链表是以出发节点为单位组织的。
• 对于每个出发节点，h 记录的是最新添加的边的编号，ne 用来链接这些边。

3. 关于 h

• h[idx] 表示节点 idx 的邻接链表的头，即最新添加的边的编号。

4. 理解 i=ne[i]

• 当 i=h[ver] 时，i 获取的是从节点 ver 出发的最新添加的边的编号。
• i=ne[i] 是沿着链表逆序遍历，即从最新添加的边依次访问之前添加的边。

代码验证

通过你的代码验证，确实可以看到逆序输出符合预期。这里再详细解释一下：

示例

假设有如下添加顺序的边：

1. add(1, 3, 9)
2. add(1, 2, 10)
3. add(1, 4, 7)

在添加这些边之后，数组可能如下：

• e = [3, 2, 4]
• ne = [-1, 0, 1]
• w = [9, 10, 7]
• h = [2, -1, -1, -1, -1]

这里的 h 数组表示节点 1 的邻接链表头部是索引 2，对应的是边 1 -> 4。

遍历顺序

遍历时：

• 开始 j = h[1]，即 j = 2。
• e[2] = 4，输出 1 -- 4，w[2] = 7，输出 7，add index: 2。
• 下一步 j = ne[2]，即 j = 1。
• e[1] = 2，输出 1 -- 2，w[1] = 10，输出 10，add index: 1。
• 下一步 j = ne[1]，即 j = 0。
• e[0] = 3，输出 1 -- 3，w[0] = 9，输出 9，add index: 0。
• 最后 j = ne[0]，即 j = -1，循环结束。

确认理解

通过这样的逆序遍历，确实符合你在代码中的输出预期，即从最新添加的边开始，逐步访问之前添加的边。

所以，你的理解和验证是正确的。如果还有任何疑问，欢迎继续讨论！