有向无环图中单源最短路径算法的运行时间

有向无环图中单源最短路径算法的运行时间取决于所使用的具体算法。下面以Dijkstra算法和Bellman-Ford算法为例进行解释，并给出代码示例。

1. Dijkstra算法： Dijkstra算法适用于没有负权边的图，其运行时间为O((V+E)logV)，其中V是顶点数，E是边数。

代码示例（使用优先队列实现）：

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = [(0, start)]

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

    return distances

2. Bellman-Ford算法： Bellman-Ford算法适用于有负权边的图，其运行时间为O(VE)，其中V是顶点数，E是边数。

代码示例：

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

    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                distance = distances[node] + weight
                if distance < distances[neighbor]:
                    distances[neighbor] = distance

    return distances

需要注意的是，以上示例代码仅展示了算法的核心思想，实际应用中可能需要对输入数据进行适当的处理和优化。另外，还有其他单源最短路径算法如SPFA算法、Floyd-Warshall算法等，其运行时间和实现方式可能有所不同。