Dijkstra算法错误与钱币兑换问题解析（算法设计作业6）

本篇文档是算法设计与分析课程的第六次作业，涉及两个主要问题：Dijkstra负边问题和钱币兑换问题，以及Kruskal算法。 1. **Dijkstra负边问题** Dijkstra算法是一种用于求解单源最短路径问题的经典算法，它假设图中的所有边都有非负权重。然而，当图中包含负权边时，如描述中提到的，Dijkstra算法可能会出错。问题的关键在于贪心策略的选择：在计算过程中，Dijkstra算法总是选择当前距离最小的节点进行扩展。如果遇到一条负权边，使得通过这条边到达的节点比已知最近节点的距离更短，但该节点已经访问过且无法再次更新其距离，就会导致算法结果不正确。例如，文档示例中，尽管2节点的实际最短路径是通过1节点再到2节点，但由于算法的局限性，它可能得到错误的结果。 2. **钱币兑换问题** 题目涉及到硬币面额是2的幂次方（如1、2、4、8等），且目标是用最少的硬币组合兑换给定的金额。解决方案是利用二进制表示法，当目标值的二进制表示中某一位为1时，说明需要一个对应面额的硬币。例如，对于某个值，如果二进制表示的最低位是1，说明需要一枚1元的硬币。给出的`CoinsofMoney`函数通过循环检查目标值的二进制形式，每次除以2并记录需要的硬币数量，直到目标值为0。 3. **Kruskal算法** Kruskal算法是一种用于求解最小生成树的并查集优化版本。它通过边的权值进行排序，然后逐个加入边，但只有当新加入的边连接的两个顶点不在同一个连通分量时（即它们的并查集根节点不同），才将这条边加入到最小生成树中。这样可以避免形成环路。`find`函数用于查找节点的根节点，并通过路径压缩操作确保高效查询。`cmp`函数定义了边的比较规则，确保边按其值从小到大排序。 总结起来，这次课程作业涵盖了最短路径算法Dijkstra在面对负权边时的问题解决策略，以及如何运用并查集优化的Kruskal算法来构建最小生成树，以及一个基于硬币面额特性寻找最少硬币组合的算法实现。这些知识点在实际编程和理论分析中都是非常重要的，能够帮助学生理解和掌握基本算法原理，并提升解决问题的能力。