C++实现带权图最短回路算法：迪杰斯特拉与弗洛伊德

本实验旨在通过C++实现数据结构实验，探索图的存储结构和最短路径算法。实验的核心内容是构建一个Graph结构体，包含顶点数量、边的数量以及邻接矩阵，以便于表示带权网络。学生需要使用迪杰斯特拉(Dijkstra)算法或弗洛伊德(Floyd-Warshall)算法来计算图中所有节点之间的最短路径。 首先，学生需要通过字符文件输入数据，建立起图的邻接矩阵。在实验设计中，迪杰斯特拉算法被重点强调，其核心思想是维护两个集合S和U，S记录已知最短路径的顶点及其长度，U则存储待处理的顶点及其到起始点的距离。算法从起点开始，每次选择U中距离最小的顶点加入S，并更新与其相邻顶点的距离。这个过程会一直持续到所有顶点都被处理过，从而找到最短路径。 对于无向图，除了应用基本的迪杰斯特拉算法外，还需要特别注意检查是否存在回路。通过对比vi到vj的最短距离加上弧度G.arcs[vi][vj]，可以确定是否存在形成回路的条件。这个过程需要对每个节点执行，以找到最短的回路。 主函数会调用Dijkstra函数多次，每次求解一个顶点到自身和其他顶点的最短路径，然后比较这些路径找到最小的回路长度（mindist）和顶点序列（minpath）。输入部分，通过fstream从字符文件读取数据，输出则使用cout流输出最短回路的相关信息。 在编程实现上，实验采用VisualC++2010环境，使用C++语言编写。关键的函数包括locate()用于查找字符对应的顶点序号，creat()用于创建图，以及Dijkstra()和Dijkstra2()分别用于求最短路径和特定顶点间的最短距离。 实验还包含了两部分测试：【测试1】针对有向图，检验算法能否正确处理有向边权重；【测试2】针对无向图，验证是否能正确识别并输出最短回路。源程序代码作为实验成果的重要组成部分，应当包含清晰的注释和逻辑结构，以便理解和复现实验过程。 通过这个实验，学生将深入理解图的存储结构和最短路径算法的实现，提高数据结构和算法的实际运用能力。同时，对编程语言的熟练运用以及问题解决策略也将得到锻炼。