农夫过河问题的 Dijkstra 算法求解

农夫过河问题是图论中经典的最短路径问题之一，它涉及一个农民和他的动物（通常假设是一个牛和一艘船）想要安全地从一岸移动到另一岸。然而，船只能承载它们两者之一，这就需要规划出一条路径，使得农民、动物都尽可能少地来回渡河。

Dijkstra算法在这种情况下并不直接适用，因为该算法设计用于寻找有向无环图（DAG）或加权边的单源最短路径，而农夫过河问题包含额外的约束条件（例如，每次只能携带一种物体过河）。解决这类问题更合适的是广度优先搜索（BFS），结合状态转移的动态规划方法，如“背包”问题的思想，逐层考虑每一步的最优选择。

以下是简单的步骤描述：
1. 初始化：设置起点（初始位置）为起始节点，目标节点为终点，所有边的权重设为无穷大，除了可以直接过河的边。
2. 开始队列：将起点加入队列，并设置其邻居节点的距离（即步数）为0。
3. 考察：从队列中取出距离最小的节点，如果该节点是目标，则结束；如果不是，更新与其相邻且未访问过的节点的距离，并标记它们为已访问。
4. 更新：对于每个相邻节点，检查当前节点携带牛或空船时到达的成本，取较小值作为新的距离。
5. 重复步骤3和4，直到找到目标节点或队列为空。