01. 单源最短路径知识（一）

[giscus[bot]]

01. 单源最短路径知识（一）

单源最短路径知识（一） 1. 单源最短路径的定义 单源最短路径（Single Source Shortest Path）：对于一个带权图 G=(V,E)，其中每条边的权重是一个实数。另外，给定 v 中的一个顶点，称之为源点。则源点到其他所有各个顶点之间的最短路径长度，称为单源最短路径。 这里的路径长度，指的是路径上各边权之和。 单源最短路径问题的核心是...

https://algo.itcharge.cn/08.Graph/04.Graph-Shortest-Path/01.Graph-Single-Source-Shortest-Path-01/

[tfhlsy010118010102]

Dijkstra解决网络延迟

class Solution(object):
    def networkDelayTime(self, times, n, k):
        """
        :type times: List[List[int]]
        :type n: int
        :type k: int
        :rtype: int
        """
        visited = set()
        graph = defaultdict(list)
        cut = [(0, k)]
        for u, v, t in times:
            graph[u].append((t, v))
        while cut:
            t, v = heapq.heappop(cut)
            if v in visited:
                continue
            visited.add(v)
            if len(visited) == n:
                return t
            for time, node in graph[v]:
                if node not in visited:
                    heapq.heappush(cut, (t+time, node))

        return -1

[Gregory616]

#这是用AI生成的Dijkstra算法

import heapq

def dijkstra(graph, start):
    """
    Implementation of Dijkstra's algorithm to find shortest paths from a single source vertex
    to all other vertices in the graph.
    
    Args:
    - graph: adjacency list representation of the graph using dictionary
             Format: {vertex: [(neighbor, weight), ...]}
    - start: starting vertex from which shortest path is calculated
    
    Returns:
    - distances: dictionary where key is the vertex and value is the shortest distance from start
    - previous_nodes: dictionary where key is the vertex and value is the previous node on the shortest path
    """
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    heapq.heapify(priority_queue)
    
    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
        
        if current_distance > distances[current_vertex]:
            continue
        
        for neighbor, weight in graph[current_vertex]:
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

# Example usage:
if __name__ == "__main__":
    graph = {
        'A': [('B', 5), ('C', 3)],
        'B': [('A', 5), ('C', 2), ('D', 1)],
        'C': [('A', 3), ('B', 2), ('D', 4)],
        'D': [('B', 1), ('C', 4)]
    }
    
    start_vertex = 'A'
    shortest_distances = dijkstra(graph, start_vertex)
    print("Shortest distances from vertex", start_vertex)
    for vertex, distance in shortest_distances.items():
        print(f"To {vertex} : {distance}")

[xiangxichen26]

是我显示的问题吗 2.2 开始全没了

[AMlhdSan]

应该不是吧。。。我也是一行都没有

[AMlhdSan]

为什么不更了啊？

[JasonCaoGit]

作者接着更新吧，网上最有用的手册了。觉得比UCB讲得全面。

[wwkk-y]

大佬太强了，什么时候更新😍