完整题目描述

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

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

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