当前位置： 面试刷题>> 目的地的最短路径 (经典算法题500道)
### 完整题目描述
**题目：码小课 - 目的地的最短路径**
给定一个无向图，图中的节点用整数表示，节点之间的连接用边表示，每条边都有一个权重（表示通过该边的成本或距离）。请编写一个函数，找到图中从一个给定源节点到另一个给定目标节点的最短路径，并返回该路径的长度（即路径上所有边的权重之和）。如果源节点到目标节点之间没有路径，则返回某个特定值（如-1）表示不存在路径。
**输入**：
- 图：以邻接表或邻接矩阵的形式表示，其中包含了节点之间的连接及其权重。
- 源节点：起始节点编号。
- 目标节点：目标节点编号。
**输出**：
- 从源节点到目标节点的最短路径长度。如果不存在路径，则返回-1。
### 示例代码
#### PHP 示例
```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 示例
```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 示例
```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
```
码小课网站中有更多相关内容分享给大家学习，包括图论、算法设计等多个方面的深度解析和实战练习。