C++实现的Floyd算法-链表版本

"这篇代码是使用C++实现的Floyd算法，通过链表来存储图的数据结构。Floyd算法，也称为Floyd-Warshall算法，是一种解决所有顶点对之间最短路径问题的动态规划算法。" 在图论中，Floyd算法是一种寻找图中所有顶点对之间最短路径的高效方法。它通过逐步考虑所有可能的中间节点来更新最短路径信息。这个算法的基本思想是，对于每一对顶点u和v，检查是否存在一个中间节点k使得经过k的路径比当前已知的u到v的路径更短。 代码首先定义了两个结构体：`Edgenode`和`Vexnode`。`Edgenode`用于表示图中的边，包含相邻顶点的索引（adj）和边的权重（weight），以及指向下一个边的指针（next）。`Vexnode`则代表图中的顶点，包含顶点的值（vex）和指向第一条边的指针（firstedge）。 `creatlist`函数用于创建图的邻接链表表示。它接受顶点数n和图的指针，然后随机生成边和权重，构建链表。对于每个顶点i，它会创建一个新边节点，设置其相邻顶点为i+1，并赋予一个1到120之间的随机权重。然后将新边添加到顶点i的链表中。 `getdistance`函数用于获取两个顶点之间的距离。它通过遍历链表找到两个顶点间的边，返回该边的权重，即两个顶点间的距离。 最后的`Floyd`函数是Floyd算法的核心。它接受顶点数n、一个二维整数数组`path`和`dist`，以及链表表示的图。`path`矩阵用于存储最短路径的信息，`dist`矩阵记录各顶点对之间的最短距离。算法通过三重循环，依次考虑所有可能的中间节点k，更新最短路径信息。如果发现通过k的路径比现有路径更短，就更新`dist`矩阵，并通过`path`矩阵记录这条路径。 这段代码实现了一个基于链表的Floyd算法，可以处理随机生成的加权有向图，找出图中所有顶点对之间的最短路径。在实际应用中，这种算法广泛应用于网络路由、交通路线规划等领域。