当前位置: 面试刷题>> 目的地的最短路径 (经典算法题500道)


完整题目描述

题目:码小课 - 目的地的最短路径

给定一个无向图,图中的节点用整数表示,节点之间的连接用边表示,每条边都有一个权重(表示通过该边的成本或距离)。请编写一个函数,找到图中从一个给定源节点到另一个给定目标节点的最短路径,并返回该路径的长度(即路径上所有边的权重之和)。如果源节点到目标节点之间没有路径,则返回某个特定值(如-1)表示不存在路径。

输入

  • 图:以邻接表或邻接矩阵的形式表示,其中包含了节点之间的连接及其权重。
  • 源节点:起始节点编号。
  • 目标节点:目标节点编号。

输出

  • 从源节点到目标节点的最短路径长度。如果不存在路径,则返回-1。

示例代码

PHP 示例

function findShortestPath($graph, $start, $end) {
    $visited = array_fill_keys(array_keys($graph), false);
    $distances = array_fill_keys(array_keys($graph), PHP_INT_MAX);
    $distances[$start] = 0;

    $queue = new SplPriorityQueue();
    $queue->insert([$start, 0], 0); // 节点和当前距离作为优先级

    while (!$queue->isEmpty()) {
        [$current, $distance] = $queue->extract();

        if ($current == $end) {
            return $distance;
        }

        if ($visited[$current]) {
            continue;
        }

        $visited[$current] = true;

        foreach ($graph[$current] as $neighbor => $weight) {
            $newDistance = $distance + $weight;
            if ($newDistance < $distances[$neighbor]) {
                $distances[$neighbor] = $newDistance;
                $queue->insert([$neighbor, $newDistance], $newDistance);
            }
        }
    }

    return -1; // 没有找到路径
}

// 示例图(邻接表形式)
$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]
];

echo findShortestPath($graph, 'A', 'D'); // 输出: 3

Python 示例

from collections import deque

def find_shortest_path(graph, start, end):
    visited = {node: False for node in graph}
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    queue = deque([(start, 0)])

    while queue:
        current, distance = queue.popleft()

        if current == end:
            return distance

        if visited[current]:
            continue

        visited[current] = True

        for neighbor, weight in graph[current].items():
            new_distance = distance + weight
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                queue.append((neighbor, new_distance))

    return -1

# 示例图(邻接表形式)
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(find_shortest_path(graph, 'A', 'D'))  # 输出: 3

JavaScript 示例

function findShortestPath(graph, start, end) {
    const visited = {};
    const distances = {};
    for (const node in graph) {
        visited[node] = false;
        distances[node] = Infinity;
    }
    distances[start] = 0;

    const queue = [[start, 0]];

    while (queue.length > 0) {
        const [current, distance] = queue.shift();

        if (current === end) {
            return distance;
        }

        if (visited[current]) {
            continue;
        }

        visited[current] = true;

        for (const [neighbor, weight] of Object.entries(graph[current])) {
            const newDistance = distance + weight;
            if (newDistance < distances[neighbor]) {
                distances[neighbor] = newDistance;
                queue.push([neighbor, newDistance]);
            }
        }
    }

    return -1;
}

// 示例图(邻接表形式)
const 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 }
};

console.log(findShortestPath(graph, 'A', 'D')); // 输出: 3

码小课网站中有更多相关内容分享给大家学习,包括图论、算法设计等多个方面的深度解析和实战练习。

推荐面试题