引言
青蛙过河是一个经典的智力游戏：河面上分布着若干石头，青蛙需要从起始石头跳跃到对岸，每次跳跃受限于青蛙的最大跳跃距离。然而，石头可能沉没、表面湿滑程度不同，使得每次跳跃都伴随着”风险代价”。如何将”最小化总风险”作为目标，找到最优过河路径？这正是Dijkstra最短路径算法在非负权图上的典型应用。本文用Java实现带风险权重的青蛙过河问题，讲解Dijkstra算法、优先队列优化与动态风险权重建模。
问题建模
将河面抽象为一个带权无向图：
– 节点：每块石头（含起始岸和对岸）
– 边：若两块石头的距离不超过青蛙最大跳跃距离，则存在一条边
– 边权：不仅考虑欧氏距离，还引入动态风险权重（如石头湿滑度、稳定性、水流速度）
– 目标：从起点到终点的总风险代价最小
风险权重函数设计：
risk(u, v) = distance(u, v) * (1 + slip_factor[v]) / stability[v]
其中 slip_factor 表示湿滑系数，stability 表示石头稳定性（0~1）。
核心算法：Dijkstra与优先队列优化
算法思路
- 图的构建：根据石头坐标和青蛙最大跳跃距离构建邻接表
- 风险权重计算：为每条边计算动态风险权重
- Dijkstra执行：
- 初始化：起点风险为0，其余为无穷大
- 优先队列（最小堆）按当前累计风险排序
- 每次取出风险最小的节点，松弛其邻接边
- 重复直到终点出队或队列为空
- 路径回溯：通过
prev[]数组记录前驱节点，输出最优路径
复杂度分析
- 时间复杂度：
O((V + E) log V)，其中V为石头数，E为边数。优先队列优化后每次取最小值为O(log V) - 空间复杂度：
O(V + E)，邻接表与距离数组
Java完整实现
import java.util.*;
/**
* 青蛙过河：Dijkstra最短路径与动态风险权重
*
* 核心思路：
* 1. 将河面石头建模为图节点，可跳跃关系建模为边
* 2. 边权引入动态风险（距离×湿滑系数÷稳定性）
* 3. 使用Dijkstra+优先队列求解起点到终点的最小风险路径
* 4. 支持路径回溯与前驱记录
*/
public class FrogRiverCrossing {
// ============ 石头节点类 ============
static class Stone {
int id;
double x, y; // 坐标位置
double slipFactor; // 湿滑系数 [0, 1]，越大越滑
double stability; // 稳定性 (0, 1]，越大越稳
boolean isStart; // 是否为起始岸
boolean isEnd; // 是否为对岸
public Stone(int id, double x, double y, double slipFactor, double stability) {
this.id = id;
this.x = x;
this.y = y;
this.slipFactor = Math.max(0, Math.min(1, slipFactor));
this.stability = Math.max(0.01, Math.min(1, stability));
}
/** 计算到另一块石头的欧氏距离 */
public double distanceTo(Stone other) {
double dx = this.x - other.x;
double dy = this.y - other.y;
return Math.sqrt(dx * dx + dy * dy);
}
/** 计算跳跃风险权重 */
public double riskTo(Stone other) {
double dist = distanceTo(other);
// 风险 = 距离 × (1 + 目标石头湿滑系数) / 目标石头稳定性
double risk = dist * (1 + other.slipFactor) / other.stability;
return risk;
}
@Override
public String toString() {
return String.format("Stone[%d](%.1f,%.1f) slip=%.2f stable=%.2f",
id, x, y, slipFactor, stability);
}
}
// ============ 图的边类 ============
static class Edge {
int to; // 目标节点
double weight; // 风险权重
public Edge(int to, double weight) {
this.to = to;
this.weight = weight;
}
}
// ============ 优先队列元素 ============
static class NodeState implements Comparable<NodeState> {
int nodeId;
double dist; // 从起点到当前节点的累计风险
public NodeState(int nodeId, double dist) {
this.nodeId = nodeId;
this.dist = dist;
}
@Override
public int compareTo(NodeState o) {
return Double.compare(this.dist, o.dist);
}
}
// ============ 游戏核心 ============
private List<Stone> stones;
private double maxJump; // 青蛙最大跳跃距离
private List<List<Edge>> graph;
public FrogRiverCrossing(double maxJump) {
this.stones = new ArrayList<>();
this.maxJump = maxJump;
}
public void addStone(Stone s) {
stones.add(s);
}
/** 根据石头位置和最大跳跃距离构建邻接表 */
public void buildGraph() {
int n = stones.size();
graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
Stone a = stones.get(i);
Stone b = stones.get(j);
double dist = a.distanceTo(b);
if (dist <= maxJump) {
// 无向图：双向添加边，权重使用目标节点的风险属性
double riskAB = a.riskTo(b);
double riskBA = b.riskTo(a);
graph.get(i).add(new Edge(j, riskAB));
graph.get(j).add(new Edge(i, riskBA));
}
}
}
}
/**
* Dijkstra算法求解最小风险路径
* @param startId 起始石头编号
* @param endId 目标石头编号
* @return 包含最短距离和路径的结果
*/
public PathResult dijkstra(int startId, int endId) {
int n = stones.size();
double[] dist = new double[n];
int[] prev = new int[n];
boolean[] visited = new boolean[n];
Arrays.fill(dist, Double.POSITIVE_INFINITY);
Arrays.fill(prev, -1);
PriorityQueue<NodeState> pq = new PriorityQueue<>();
dist[startId] = 0;
pq.offer(new NodeState(startId, 0));
while (!pq.isEmpty()) {
NodeState cur = pq.poll();
int u = cur.nodeId;
if (visited[u]) continue;
visited[u] = true;
if (u == endId) {
break; // 终点已确定最短距离
}
for (Edge e : graph.get(u)) {
int v = e.to;
if (visited[v]) continue;
double newDist = dist[u] + e.weight;
if (newDist < dist[v]) {
dist[v] = newDist;
prev[v] = u;
pq.offer(new NodeState(v, dist[v]));
}
}
}
// 回溯路径
List<Stone> path = new ArrayList<>();
if (dist[endId] < Double.POSITIVE_INFINITY) {
int at = endId;
while (at != -1) {
path.add(stones.get(at));
at = prev[at];
}
Collections.reverse(path);
}
return new PathResult(dist[endId], path, prev);
}
/** 获取指定节点的所有邻接节点（用于调试） */
public void printGraph() {
for (int i = 0; i < graph.size(); i++) {
System.out.print(stones.get(i) + " -> ");
for (Edge e : graph.get(i)) {
System.out.printf("[%d w=%.2f] ", e.to, e.weight);
}
System.out.println();
}
}
// ============ 结果类 ============
static class PathResult {
double totalRisk;
List<Stone> path;
int[] prev;
public PathResult(double totalRisk, List<Stone> path, int[] prev) {
this.totalRisk = totalRisk;
this.path = path;
this.prev = prev;
}
@Override
public String toString() {
if (path.isEmpty()) {
return "无法到达终点！";
}
StringBuilder sb = new StringBuilder();
sb.append(String.format("最小总风险: %.4f\n最优路径 (%d 步):\n", totalRisk, path.size() - 1));
for (int i = 0; i < path.size(); i++) {
sb.append(" ").append(path.get(i));
if (i < path.size() - 1) {
double stepRisk = path.get(i).riskTo(path.get(i + 1));
sb.append(String.format(" --[risk=%.2f]--> ", stepRisk));
}
sb.append("\n");
}
return sb.toString();
}
}
// ============ 主程序 ============
public static void main(String[] args) {
// 场景：河宽100米，青蛙最大跳25米
FrogRiverCrossing game = new FrogRiverCrossing(25.0);
// 起始岸 (0, 0)
Stone start = new Stone(0, 0, 0, 0, 1.0);
start.isStart = true;
game.addStone(start);
// 随机生成河中的石头
Random rand = new Random(123);
int stoneCount = 15;
for (int i = 1; i <= stoneCount; i++) {
double x = 5 + rand.nextDouble() * 90; // x: 5~95
double y = -20 + rand.nextDouble() * 40; // y: -20~20，模拟河的宽度方向
double slip = rand.nextDouble() * 0.8; // 湿滑度 0~0.8
double stable = 0.3 + rand.nextDouble() * 0.7; // 稳定性 0.3~1.0
game.addStone(new Stone(i, x, y, slip, stable));
}
// 对岸 (100, 0)
Stone end = new Stone(stoneCount + 1, 100, 0, 0, 1.0);
end.isEnd = true;
game.addStone(end);
// 建图并求解
game.buildGraph();
System.out.println("=== 青蛙过河：Dijkstra最小风险路径 ===\n");
System.out.println("河面石头分布：");
for (Stone s : game.stones) {
System.out.println(" " + s);
}
PathResult result = game.dijkstra(0, game.stones.size() - 1);
System.out.println("\n" + result);
// 对比：如果忽略风险权重，只按距离计算
System.out.println("\n【对比】若仅按欧氏距离最短（不考风险）：");
// 此时所有边权为distance，Dijkstra退化为普通最短路
// 为简化，输出实际跳跃距离之和
if (!result.path.isEmpty()) {
double totalDist = 0;
for (int i = 0; i < result.path.size() - 1; i++) {
totalDist += result.path.get(i).distanceTo(result.path.get(i + 1));
}
System.out.printf("路径总距离: %.2f 米\n", totalDist);
}
}
}
关键代码解析
1. 动态风险权重
public double riskTo(Stone other) {
double dist = distanceTo(other);
return dist * (1 + other.slipFactor) / other.stability;
}
风险函数将物理距离、环境属性（湿滑度）和结构属性（稳定性）融合为单一代价指标。这种设计使得Dijkstra算法在求解时自动”避开”湿滑且不稳定的石头，即使它们物理距离较近。
2. 优先队列优化
PriorityQueue<NodeState> pq = new PriorityQueue<>();
Java的 PriorityQueue 基于二叉堆实现，提供 O(log V) 的插入和删除最小值操作。相比普通数组找最小值的 O(V)，整体复杂度从 O(V²) 优化到 O((V + E) log V)，在稀疏图（河面石头分布稀疏）上优势显著。
3. 提前终止
if (u == endId) break;
Dijkstra算法保证当目标节点第一次从优先队列中取出时，其距离值已经是最短的。因此可以立即终止搜索，无需遍历全图。
扩展思考
- 负权边处理：若引入”顺流加速”等负权因素，Dijkstra不再适用，需改用Bellman-Ford或SPFA算法
- 多目标优化：同时优化风险与跳跃次数，可引入帕累托前沿或加权求和策略
- 实时动态图：石头随时间沉没（边删除）或新石头浮起（边插入），可用动态图最短路算法维护
总结
本文通过青蛙过河游戏，将Dijkstra最短路径算法与动态风险建模相结合。核心贡献在于：
– 设计了融合距离、湿滑度和稳定性的风险权重函数
– 使用优先队列将Dijkstra复杂度优化至 O((V + E) log V)
– 提供了完整的路径回溯与前驱记录机制
该框架可直接迁移至导航路线规划、网络路由优化、机器人路径规划等实际领域。
