题目描述补充

题目：网络延迟时间计算

在一个分布式系统中，存在多个服务器节点，每个节点之间可以相互通信。给定一个服务器节点的列表和一个二维数组，其中二维数组的每个元素表示两个节点之间的通信延迟时间（单位：毫秒）。数组中的元素形如[A, B, delay]，表示从节点A到节点B的通信延迟为delay毫秒。注意，从节点B到节点A的延迟可能不同，并且某些节点对之间可能没有直接的通信路径（即没有直接的延迟时间给出）。

目标是编写一个函数，该函数接受上述的节点列表和二维数组作为输入，然后返回从某个指定源节点到所有其他节点的最短延迟时间。如果某个节点无法从源节点到达，则返回无穷大（例如，使用PHP中的PHP_INT_MAX，Python中的float('inf')，或JavaScript中的Number.POSITIVE_INFINITY）。

示例代码

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 示例

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 示例

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);

码小课网站中有更多相关内容分享给大家学习，涵盖算法、数据结构、网络编程等多个领域，帮助大家更好地掌握编程技能。