四、用go语言，对输入链长度为 n 的矩阵链乘法问题，描述其子问题图：它包含多少个顶点?包含多少条边?这些边分别连接哪些顶点?

文心一言：

五、假定在一个权重函数为w的有向图上运行 Johnson 算法。证明：如果图包含一条权重为 0 的环路，那么对于环路上的每条边，。如果要写代码，请用go语言。

二、在 Johnson 算法里，在集合 V 中加入新结点 s 产生 V' 的目的是什么？如果要写代码，请用go语言。

chatgpt：

二、请给出下面差分约束系统的可行解或证明该系统没有可行解。

六、我们怎样才能使用 Floyd-Warshall 算法的输出来检测权重为负值的环路？如果要写代码，请用go语言。

chatgpt：

一、请在图25-2上使用Johnson算法来找到所有结点对之间的最短路径。给出算法计算出的和值。如果要写代码，请用go语言。

chatgpt：

九、假定我们可以在的时间内计算出一个有向无环图的传递闭包，其中是一个自变量为和的单调递增函数。证明：计算一个通用的有向图，的传递闭包的时间复杂度为。如果要写代码，请用go语言。

八、给出一个〇(VE)时间复杂度的算法来计算有向图G=(V,E)的传递闭包。如果要写代码，请用go语言。

chatgpt：

这个是图论的倒数第二章。我会着重讲解最小生成树和拓扑排序两个算法。如果哪些地方我写错的，或者没写清楚的，可以评论区吐槽~

先看一道洛谷上面的题目。