当前位置： 面试刷题>> 网络延迟时间 (经典算法题500道)
### 题目描述补充
**题目：网络延迟时间计算**
在一个分布式系统中，存在多个服务器节点，每个节点之间可以相互通信。给定一个服务器节点的列表和一个二维数组，其中二维数组的每个元素表示两个节点之间的通信延迟时间（单位：毫秒）。数组中的元素形如`[A, B, delay]`，表示从节点A到节点B的通信延迟为`delay`毫秒。注意，从节点B到节点A的延迟可能不同，并且某些节点对之间可能没有直接的通信路径（即没有直接的延迟时间给出）。
目标是编写一个函数，该函数接受上述的节点列表和二维数组作为输入，然后返回从某个指定源节点到所有其他节点的最短延迟时间。如果某个节点无法从源节点到达，则返回无穷大（例如，使用PHP中的`PHP_INT_MAX`，Python中的`float('inf')`，或JavaScript中的`Number.POSITIVE_INFINITY`）。
### 示例代码
#### PHP 示例
```php
function findShortestPaths($nodes, $delays, $source) {
$n = count($nodes);
$distances = array_fill(0, $n, PHP_INT_MAX);
$distances[$source] = 0;
$queue = new SplPriorityQueue();
$queue->insert([$source, 0], 0);
while (!$queue->isEmpty()) {
[$current, $currentDistance] = $queue->extract();
foreach ($delays as $delay) {
[$from, $to, $d] = $delay;
$indexFrom = array_search($from, $nodes);
$indexTo = array_search($to, $nodes);
if ($indexFrom === $current && $distances[$indexTo] > $currentDistance + $d) {
$distances[$indexTo] = $currentDistance + $d;
$queue->insert([$to, $distances[$indexTo]], -$distances[$indexTo]); // 使用负值来确保队列是最小堆
}
}
}
return $distances;
}
// 示例用法
$nodes = ['A', 'B', 'C', 'D'];
$delays = [['A', 'B', 1], ['B', 'C', 2], ['A', 'C', 5], ['C', 'D', 1]];
$source = 'A';
$result = findShortestPaths($nodes, $delays, $source);
print_r($result);
```
#### Python 示例
```python
def find_shortest_paths(nodes, delays, source):
n = len(nodes)
distances = [float('inf')] * n
distances[nodes.index(source)] = 0
queue = [(0, source)]
while queue:
current_distance, current_node = heapq.heappop(queue)
index = nodes.index(current_node)
for delay in delays:
from_node, to_node, d = delay
if from_node == current_node and distances[nodes.index(to_node)] > current_distance + d:
distances[nodes.index(to_node)] = current_distance + d
heapq.heappush(queue, (distances[nodes.index(to_node)], to_node))
return distances
# 示例用法
nodes = ['A', 'B', 'C', 'D']
delays = [['A', 'B', 1], ['B', 'C', 2], ['A', 'C', 5], ['C', 'D', 1]]
source = 'A'
result = find_shortest_paths(nodes, delays, source)
print(result)
```
#### JavaScript 示例
```javascript
function findShortestPaths(nodes, delays, source) {
const n = nodes.length;
const distances = new Array(n).fill(Number.POSITIVE_INFINITY);
distances[nodes.indexOf(source)] = 0;
const queue = [];
queue.push([source, 0]);
while (queue.length > 0) {
[current, currentDistance] = queue.shift();
const index = nodes.indexOf(current);
for (const [from, to, d] of delays) {
if (from === current && distances[nodes.indexOf(to)] > currentDistance + d) {
distances[nodes.indexOf(to)] = currentDistance + d;
queue.push([to, distances[nodes.indexOf(to)]]);
}
}
}
return distances;
}
// 示例用法
const nodes = ['A', 'B', 'C', 'D'];
const delays = [['A', 'B', 1], ['B', 'C', 2], ['A', 'C', 5], ['C', 'D', 1]];
const source = 'A';
const result = findShortestPaths(nodes, delays, source);
console.log(result);
```
**码小课网站中有更多相关内容分享给大家学习**，涵盖算法、数据结构、网络编程等多个领域，帮助大家更好地掌握编程技能。