配套光盘/正文包含的程序片段/0x61 shortest_path.cpp Floyd传递闭包一处有误

[lingyunvoid]

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) d[i][i] = 1;
	for (int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		d[x][y] = d[y][x] = 1;
	}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				d[i][j] |= d[i][k] & d[k][j];
}

for (int i = 1; i <= n; i++) d[i][i] = 1; 这一行应去掉，且原书P360所述有误：

特别地，$d[i][i]$ 始终为 $1$。

可以很轻松举出反例，如 <「小于」关系显然具有传递性，即 a<b,b<c 可以推出 a<c，但显然 a<a 不成立，因此 不能将 $d[i][i]$ 初始化为 $1$。