寻找最小生成树及最短路径

寻找最小生成树（Minimum Spanning Tree, MST）和最短路径是图论中两个基本的概念。它们在计算机科学中有着广泛的应用，特别是在网络设计、路由算法以及优化问题中。

**最小生成树**：
最小生成树是指在一个加权无向图中，选择一组边使得这些边连接所有的顶点，并且这些边的总权重（边的长度或代价）是最小的。常见的算法有Prim算法、Kruskal算法和Floyd-Warshall算法，其中Prim算法是从一个顶点开始，每次添加一条连接当前树与未加入顶点中成本最低的边；Kruskal算法则是从小到大对所有边排序，然后依次加入不形成环的边。

**最短路径**：
最短路径是指在有向或无向图中，从一个起点到其他所有点的路径中，具有最小代价（或长度）的路径。有多种算法可以找到最短路径，比如Dijkstra算法（适用于非负权边图）、Floyd-Warshall算法（适用于所有图，包括负权边但不含负权循环）和A*搜索算法（适用于带启发信息的图）。Floyd-Warshall算法可以同时求出任意两点之间的最短路径。