python 구현 dijkstra 최 단 경로 알고리즘
메모:Dijkstra 알고리즘 은 네 거 티 브 를 포함 한 그림 을 처리 할 수 없습니다.
# dijkstra ， ，
def dijkstra(graph,src):
# ，
if graph is None:
return None
nodes = [i for i in range(len(graph))] #
visited=[] #
if src in nodes:
visited.append(src)
nodes.remove(src)
else:
return None
distance={src:0} #
for i in nodes:
distance[i]=graph[src][i] #
# print(distance)
path={src:{src:[]}} #
k=pre=src
while nodes:
mid_distance=float('inf')
for v in visited:
for d in nodes:
new_distance = graph[src][v]+graph[v][d]
if new_distance < mid_distance:
mid_distance=new_distance
graph[src][d]=new_distance #
k=d
pre=v
distance[k]=mid_distance #
path[src][k]=[i for i in path[src][pre]]
path[src][k].append(k)
#
visited.append(k)
nodes.remove(k)
print(visited,nodes) #
return distance,path
if __name__ == '__main__':
graph_list = [ [0, 2, 1, 4, 5, 1],
[1, 0, 4, 2, 3, 4],
[2, 1, 0, 1, 2, 4],
[3, 5, 2, 0, 3, 3],
[2, 4, 3, 4, 0, 1],
[3, 4, 7, 3, 1, 0]]
distance,path= dijkstra(graph_list, 0) # 0
print(distance,path)
최 단 경로 출력:
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
로마 숫자를 정수로 또는 그 반대로 변환그 중 하나는 로마 숫자를 정수로 변환하는 함수를 만드는 것이었고 두 번째는 그 반대를 수행하는 함수를 만드는 것이었습니다. 문자만 포함합니다'I', 'V', 'X', 'L', 'C', 'D', 'M' ; 문자열이 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
