[イコタイ]最短パスアルゴリズム-マルチ出口最短パスアルゴリズム

最短パスの問題

マルチ出口最短パスアルゴリズムの概要

マルチアウトレット最短パスアルゴリズム

イルケメは一瞬にしてもっと短い経路を見つけた!
それは.

マルチタスクアルゴリズムマルチタスクアルゴリズム:操作プロセスの理解

1を起点として1から、残りの無限量をテーブルに記入!
そして1に繋がるノードまでの距離を書きます!
と1以降1に接続されたノードのうち最も距離の近いノード4から、4に接続されたノードを基準に距離を再探索!

4アクセス処理を行い、まだアクセスしていないノードの中から、最短距離で最短の2を選択し、2から距離を初期化します!

同じように歌う!
からこのまま進めば、最後のノードは処理しなくても大丈夫です.

マルチアウトプットアルゴリズムの特徴

マルチアウトレットアルゴリズム:簡単な実施方法

各ステップ

のアクセスされていないノードから最短距離のノードを選択するには、各ステップで1次元テーブルのすべての要素をチェックします(順次参照).

マルチアウトプットアルゴリズム:簡単な実装方法(Python)

# 다익스트라 알고리즘 
import sys
from turtle import distance 
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미 하는 10억 

#노드의 개수, 간선의 개수 입력받기
n,m = map(int,input().split())
# start num 
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트 만들기 
graph =[[] for _ in range(n+1)] 
#방문한 적이 있는지 체크하는 목적의 리스트 제작 
visted = [False] * (n+1)

# 모든 간선 정보를 입력받기 
for _ in range(m):
    a,b,c = map(int,input().split())
    #a번 노드에서 b번 노드로 가는 비용이 C
    graph[a].append((b,c))

# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환하는 함수 
def get_smallest_node():
    min_value = INF 
    idx= 0 # 가장 최단 거리가 짧은 노드 번호 (인덱스) 
    for i in range(1,n+1):
        if (distance[i]<min_value and not visted[i]) : #만약 거리가 최소설정거리(무한)보다 작고, 방문하지 않은 노드라면
            min_value = distance[i]
            idx = i
    return idx 

def dijkstra(start):
    # 시작 노드에 대해 초기화 
    distance[start] = 0
    visted[start] = True 
    for j in graph[start]:
        distance[j[0]] = j[1] #j[0] : b번 노드 j[1]: 비용 
        #start 에서 j[0]번 노드로 가는 비용 j[1]
    #시작 노드를 제외한 전체 n-1개의 노드에 대한 반복 
    for i in range(n-1):
        # 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리 
        now = get_smallest_node()
        visted[now] = True 
        # 현재 노드와 연겨ㅕㄹ된 다른 노드를 확인 
        for j in graph[now]:
            cost = distance[now]+j[1]
            #현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우 
            if cost<distance[j[0]]:
                distance[j[0]] = cost 
                
dijkstra(start)

for i in range(1,n+1):
    if distance[i] == INF :
        print("도달못함")
    else : #도달할 수 있는 경우 거리를 출력 
        print(distance[i]) 
    

ほほほ
これは意外にも簡単な実現で、私はジャガイモです.

マルチカーブアルゴリズム:簡単な実装方法の性能分析

これらの問題を解決するために、簡単な実施方法がある.別の実現方法を考えなければならない.
彼のために優先順位キューを勉強しましょう.

優先キュー

お尻

ホール~~~リストよりいい
hipは木構造の資料構造である

hipライブラリの使用例:最小hip

import heapq 

#오름차순 힙 정렬 
def heapsort(iterable):
    h = []
    result = []
    #모든 원소를 차례대로 힙에 삽입 
    for value in iterable:
        heapq.heappush(h,value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h))
        #우선순위가 높은거부터 뽑아낸다.
    return result 

result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)
#[0,1,2...8,9]

ビオは並んだりお尻を並べたりしています

hipライブラリの使用例:最大hip

import heapq 

#내림차순 힙 정렬(Heap Sort)
def heapsort(iterable):
    h = []
    result = []
    for value in iterable:
        heapq.heappush(h,-value)
    for i in range(len(h)):
        result.append(-heapq.heappop(h))
    return result 
result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(reuslt)
#[9,8,7...1,0]

value-値を逆さに...!

マルチアウトプットアルゴリズム:改善された実施方法

マルチタスクアルゴリズムマルチタスクアルゴリズム:操作プロセス(優先キュー)の理解

マルチアウトプットアルゴリズム:改善された実施方法

# 다익스트라 알고리즘 
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미 하는 10억 

#노드의 개수, 간선의 개수 입력받기
n,m = map(int,input().split())
# start num 
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트 만들기 
graph =[[] for _ in range(n+1)] 
#최단 거리 테이블 모두 무한 초기화 
distance = [INF]*(n+1)

# 모든 간선 정보를 입력받기 
for _ in range(m):
    a,b,c = map(int,input().split())
    #a번 노드에서 b번 노드로 가는 비용이 C
    graph[a].append((b,c))

def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여 큐에 삽입 
    heapq.heappush(q,(0,start))
    distance[start] = 0
    while q:
        #가장 최단 거리가 짧은 노드에 대한 정보 꺼내기 
        dist, now = heapq.heappop(q)
        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시 
        if distance[now]<dist:
            continue
        # 현재 노드와 연결된 다른 인접한 노드들을 확인 
        for i in graph[now]:
            cost = dist + i[1]
            # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우 
            if cost < distance[i[0]]:
                distance[i[0]] = cost 
                heapq.heappush(q,(cost,i[0])) 

# 다익스트라 알고리즘을 수행 
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력 
for i in range(1,n+1):
    if distance[i]==INF:
        print("못감")
    else:
        print(distance[i])

マルチアウトプットアルゴリズム:改善された実施方法の性能を分析する