递归vs迭代：Java实现最短路径算法的对比解析

.png)
# 1. 最短路径问题的理论基础

最短路径问题（Shortest Path Problem, SPP）是图论中的一个经典问题，也是计算几何、网络优化和运筹学等领域中一个核心议题。这一问题的核心是在一个有权重的图中找到两个顶点之间的最短路径。根据图的性质，最短路径问题又可以细分为有向图和无向图的最短路径问题，以及有无负权重边的最短路径问题。

## 1.1 图论中的路径与距离

在图论中，路径（Path）是指在一个图中，从一个顶点到另一个顶点所经过的一系列边的序列。路径的长度是路径上所有边权重的总和。当我们要计算从起点到终点的最短路径时，就是寻找一条路径，使得路径的长度最小。

## 1.2 最短路径问题的类型

根据不同的约束条件，最短路径问题可分为多种类型：

- 单源最短路径（SSSP）：确定图中从单一源点到所有其他顶点的最短路径。
- 多源最短路径：确定图中从一组源点到所有其他顶点的最短路径。
- 单对最短路径：确定图中从一对给定顶点间的最短路径。
- 所有点对最短路径（APSP）：确定图中所有顶点对之间的最短路径。

本章我们将重点介绍单对最短路径和单源最短路径问题，这两种问题的解决方法可以为更复杂的最短路径问题奠定基础。接下来的章节将深入探讨解决这些问题的不同算法，包括递归和迭代方法。

# 2. 递归算法在最短路径问题中的应用

### 2.1 递归算法的理论和特点

#### 2.1.1 递归的基本概念和结构
递归是一种编程技术，它允许函数调用自身以解决问题。这种技术在处理有自相似性质的问题时尤其有用，如树和图的遍历、分治算法等。递归算法通常包含两个基本部分：基本情况（base case）和递归情况（recursive case）。

def factorial(n):
    if n == 0: # 基本情况
        return 1
    else: # 递归情况
        return n * factorial(n - 1)

print(factorial(5))  # 输出：120

递归的基本概念要求我们理解递归的两部分：
- **基本情况**：递归的最简单形式，是递归调用的终点，避免了无限递归的发生。
- **递归情况**：定义问题如何分解为更小的子问题，并将结果组合以解决原问题。

#### 2.1.2 递归在图论中的应用
在图论中，递归可用于解决许多问题，例如遍历图的节点（深度优先搜索或DFS）、计算图的连通分量，或寻找最短路径。以DFS为例，它使用递归或栈来遍历图的节点，直到达到一个节点的尽头或访问了所有可达节点。

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node)  # 访问节点
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

在图论中应用递归时，要注意避免重复访问节点，这通常通过维护一个已访问节点的集合来实现。

### 2.2 递归算法求解最短路径问题的实例分析

#### 2.2.1 迪杰斯特拉算法的递归版本
迪杰斯特拉（Dijkstra）算法是用于计算图中单源最短路径的经典算法。虽然它通常以非递归方式实现，但可以设计其递归版本。

def dijkstra_recursive(graph, start, visited=None, distance=None):
    if visited is None:
        visited = set()
    if distance is None:
        distance = {vertex: float('infinity') for vertex in graph}
    distance[start] = 0

    def relax(node):
        for neighbor, weight in graph[node].items():
            if neighbor not in visited:
                if distance[node] + weight < distance[neighbor]:
                    distance[neighbor] = distance[node] + weight
                    # 递归调用 relax 函数继续更新距离
                    relax(neighbor)

    # 基本情况：所有节点都被访问
    if len(visited) == len(graph):
        return distance

    # 找到最近的未访问节点
    min_distance = float('infinity')
    min_node = None
    for node in graph:
        if node not in visited and distance[node] < min_distance:
            min_distance = distance[node]
            min_node = node

    # 递归情况：访问最近的未访问节点并更新距离
    visited.add(min_node)
    relax(min_node)

    return dijkstra_recursive(graph, start, visited, distance)

# 示例图的表示
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

print(dijkstra_recursive(graph, 'A'))

在这个递归版本的Dijkstra算法中，`relax` 函数用于更新节点间距离，并递归调用自身以继续查找最短路径。

#### 2.2.2 贝尔曼-福特算法的递归实现
贝尔曼-福特（Bellman-Ford）算法是另一种用于寻找有向图中单源最短路径的算法，特别是当图中包含负权边时。它也可递归地实现。

def bellman_ford_recursive(graph, start, distance=None, predecessor=None):
    if distance is None:
        distance = {vertex: float('infinity') for vertex in graph}
        distance[start] = 0
    if predecessor is None:
        predecessor = {vertex: None for vertex in graph}

    def relax(edge):
        src, dest, weight = edge
        if distance[src] + weight < distance[dest]:
            distance[dest] = distance[src] + weight
            predecessor[dest] = src
            return True
        return False

    # 基本情况：所有边都已放松，或在经过 V-1 次迭代后出现负权重循环
    if len(distance) == 1:  # 无节点图的特殊情况
        return distance, predecessor
    relaxed = False
    for edge in graph.values():  # graph 是边的集合
        relaxed = relax(edge) or relaxed
    return bellman_ford_recursive(graph, start, distance, predecessor) if relaxed else (distance, predecessor)

#