O（V+ElogV）时间复杂度下的Python-Dijkstra算法

Question

我想用Python实现上述算法。Dijkstra算法的时间复杂度是O（V2），但我想使用最小优先级队列来实现它，所以它下降到O（V+ElogV）

这里有一个输入示例：

程序应该有两个问题，src:0 dest:2和src:1 dest:2。输入将提供3个顶点，还将提供3条边，所有这些边都用一条空线分隔

2
3
3

0   2
1   2

2   0
-4  1
6   3

1   0
1   2
0   2

解决方案：

5.0     10.2

这是我当前的代码：

import math
import sys
 
def build_graph(edges, weights, e):
    graph = edges

    for i in range(e):
        graph[i].append(weights[i])
        
    return graph

def debug():
    print(pontparok)
    print(csucsok)
    print(utszakaszok)
    print(hosszak)

def read(n, bemenet):
    for i in range(n):
        temp = input().split("\t")
        bemenet[i] = temp
        bemenet[i][0] = int(bemenet[i][0])
        bemenet[i][1] = int(bemenet[i][1])

def dijkstra(edges, src, dest, n):
    dist = [0] * n
    current = src

    for i in range(n):
        dist[i] = sys.maxsize
    dist[src] = 0

    explored = [False] * n

    q = 0
    while not explored[dest] and q < 1000:
        q += 1
        min = sys.maxsize
        minVertex = current
        for edge in edges:
            if edge[0] == current and not explored[edge[1]]:
                if min > dist[edge[1]]:
                    min = dist[edge[1]]
                    minVertex = edge[1]
            elif edge[1] == current and not explored[edge[0]]:
                if min > dist[edge[0]]:
                    min = dist[edge[0]]
                    minVertex = edge[0]
        
        current = minVertex
        explored[current] = True
        for edge in edges:
            if edge[0] == current:
                if dist[current] + edge[2] < dist[edge[1]]:
                    dist[edge[1]] = dist[current] + edge[2]
            elif edge[1] == current:
                if dist[current] + edge[2] < dist[edge[0]]:
                    dist[edge[0]] = dist[current] + edge[2] 
    
    return round(dist[dest], 2)

p = int(input())
n = int(input())
e = int(input())
input()

pontparok = [[0] * 2] * p
csucsok = [[0] * 2] * n
utszakaszok = [[0] * 2] * e
hosszak = [0] * e

read(p, pontparok)
input()
read(n, csucsok)
input()
read(e, utszakaszok)

for i in range(e):
    hosszak[i] = math.sqrt(pow((csucsok[utszakaszok[i][0]][0] - csucsok[utszakaszok[i][1]][0]), 2) + pow((csucsok[utszakaszok[i][0]][1] - csucsok[utszakaszok[i][1]][1]), 2))

#debug()

graph = build_graph(utszakaszok, hosszak, e)
#print(hosszak)

for i in range(p):
    if i == p - 1:
        print(dijkstra(graph, pontparok[i][0], pontparok[i][1], n))
    else:
        print(dijkstra(graph, pontparok[i][0], pontparok[i][1], n), end="\t")

Answer 1

import heapq
import math

def read(n, bemenet):
    for i in range(n):
        temp = input().split("\t")
        bemenet[i] = temp
        bemenet[i][0] = int(bemenet[i][0])
        bemenet[i][1] = int(bemenet[i][1])


def dijkstra(graph, starting_vertex, destination_vertex):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[starting_vertex] = 0

    pq = [(0, starting_vertex)]
    while len(pq) > 0:
        current_distance, current_vertex = heapq.heappop(pq)

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return round(distances[destination_vertex], 2)

def build_graph(edges, weights, e):
    graph = edges

    for i in range(e):
        graph[i].append(weights[i])
        
    return graph


p = int(input())
n = int(input())
e = int(input())
input()

pontparok = [[0] * 2] * p
csucsok = [[0] * 2] * n
utszakaszok = [[0] * 2] * e
hosszak = [0] * e

read(p, pontparok)
input()
read(n, csucsok)
input()
read(e, utszakaszok)

for i in range(e):
    hosszak[i] = math.sqrt(pow((csucsok[utszakaszok[i][0]][0] - csucsok[utszakaszok[i][1]][0]), 2) + pow((csucsok[utszakaszok[i][0]][1] - csucsok[utszakaszok[i][1]][1]), 2))

graph2 = build_graph(utszakaszok, hosszak, e)
graph = { }
[graph.setdefault(i, []) for i in range(n)] 
for i in range(n):
    graph[i] = {}
for edge in graph2:
    graph[edge[0]].update({edge[1]: edge[2]})
    graph[edge[1]].update({edge[0]: edge[2]})

for i in range(p):
    if i == p - 1:
        print(dijkstra(graph, pontparok[i][0], pontparok[i][1]))
    else:
        print(dijkstra(graph, pontparok[i][0], pontparok[i][1]), end="\t")