C语言实现Dijkstra与Floyd算法

"这篇资源主要介绍了C语言中的两种重要算法：Dijkstra算法和Floyd算法。Dijkstra算法用于寻找图中两点之间的最短路径，而Floyd算法则用于求解所有点对之间的最短路径。" Dijkstra算法是图论中的经典算法之一，主要用于找出从起点到所有其他顶点的最短路径。在这个C语言实现中，Dijkstra算法的基本思想是使用贪心策略，每次选取当前未访问顶点中距离起点最近的一个进行扩展。算法的关键在于维护一个优先队列（这里用数组模拟），并将起点的距离设为0，其他顶点的距离设为无穷大（表示未到达）。在每一步迭代中，找到未访问顶点中距离最小的一个，更新与其相邻且未访问过的顶点的距离，并记录下前驱节点。 代码中，`visited[]`数组用来标记每个顶点是否已被访问，`dis[]`存储从起点到各个顶点的最短距离，`per[]`记录到达每个顶点的前驱节点。Dijkstra函数接收两个参数，一个是顶点数`n`，另一个是起点`x`。在循环中，首先找到未访问顶点中距离最小的`p`，然后更新与`p`相邻的所有未访问顶点的距离。 Floyd算法，又称为Floyd-Warshall算法，是一种解决所有顶点对之间最短路径的动态规划方法。它通过逐步考虑中间节点来更新最短路径。在C语言实现中，Floyd算法通过三层循环完成：外层循环`k`遍历所有可能的中间节点，中间两层循环`i`和`j`遍历所有顶点对。对于每一对`i`和`j`，检查通过`k`作为中间节点的路径是否比已知的最短路径更短。如果更短，则更新最短路径和对应的路径信息。同时，当路径长度相等时，选择通过更优路径到达的节点。 在输出部分，程序会打印出从`x`到`y`的最短路径。通过`per[]`数组，可以回溯出路径上的每一个节点，直到到达目标节点`y`。 `in[]`数组在此段代码中未被使用，可能是遗留的未删除的变量，或者在完整版本的代码中有其特定用途。 这两种算法在计算机科学和图论中有着广泛的应用，尤其是在网络路由、最优化问题和图形处理等领域。学习和掌握这些算法对于理解和解决实际问题至关重要。