dijkstra算法处理有向图

### Dijkstra算法在有向图中的应用

Dijkstra算法用于计算加权有向图中单源最短路径问题。该算法能够有效地找出从起始节点到其他所有节点的最短路径长度，并记录下具体的路径信息[^1]。

对于给定的一个带权重的有向图G=(V,E)，其中V代表顶点集合，E表示边集；每条边上关联着一个非负实数作为其成本或距离d(u,v)≥0, u∈V, v∈V。设s为指定起点，则通过执行如下过程来求解：

#### 初始化阶段
- 创建一个数组`dist[]`, 对于每一个结点v初始化`dist[v]=∞`(无穷大), 表示未知最小代价.
- 设置`dist[s]=0`因为到达自身的花费自然为零.

#### 主循环迭代更新
直到所有的顶点都被访问过为止，在每次迭代时做两件事：
- 找出当前未被标记且具有最小临时键值(即估计距离)`u=min{ dist[u]|u ∈ V-U }`.
- 将此顶点加入已处理过的列表U内并对其邻接表里的各个项进行松弛操作：如果发现更优路线则调整对应目标节点w的新估算值`if (dist[w]>dist[u]+weight[u][w]) then update`.

当上述流程结束之后，就可以得到由原点出发至各终点间的最优行走方案了。

下面给出Python版本的具体实现方式:

import heapq

def dijkstra(graph, start):
    n = len(graph)
    distances = {node: float('inf') for node in range(n)}
    previous_nodes = {node: None for node in range(n)}
    distances[start] = 0
    
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_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
                previous_nodes[neighbor] = current_node
                heapq.heappush(priority_queue, (distance, neighbor))
                
    return distances, previous_nodes


graph_representation = {
    0: {1: 7, 2: 9, 5: 14},
    1: {2: 10, 3: 15},
    2: {3: 11, 5: 2},
    3: {4: 6},
    4: {},
    5: {4: 9}
}

start_vertex = 0  
shortest_distances, path_to_vertices = dijkstra(graph_representation, start_vertex)

print(f"The shortest paths from vertex {start_vertex} are:")
for target in sorted(shortest_distances):
    print(f"To vertex {target}: cost={shortest_distances[target]}")

这段代码定义了一个函数 `dijkstra()` 来接收输入参数——图形结构以及初始位置索引号。它返回两个字典对象分别保存最终测得的成本数值还有重建完整行程所需的前驱指引链表。最后部分展示了一组测试数据及其调用结果输出样例[^2]。