木。

特長

用語

適用

バイナリツリー

バイナリナビゲーションツリーBST

グラフとの相違

最短パスナビゲーションアルゴリズムShortest Path

マルチアウトレットアルゴリズム

さぎょう

コード#コード#

import sys
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())
start = int(input())
# 주어지는 그래프 정보 담는 N개 길이의 리스트
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)  # 방문처리 기록용
distance = [INF] * (n+1)   # 거리 테이블용

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

# 방문하지 않은 노드이면서 시작노드와 최단거리인 노드 반환
def get_smallest_node():
    min_value = INF
    index = 0
    for i in range(1, n+1):
        if not visited[i] and distance[i] < min_value:
            min_value = distance[i]
            index = i
    return index

# 다익스트라 알고리즘
def dijkstra(start):
    # 시작노드 -> 시작노드 거리 계산 및 방문처리
    distance[start] = 0
    visited[start] = True
    # 시작노드의 인접한 노드들에 대해 최단거리 계산
    for i in graph[start]:
        distance[i[0]] = i[1]

    # 시작노드 제외한 n-1개의 다른 노드들 처리
    for _ in range(n-1):
        now = get_smallest_node()  # 방문X 면서 시작노드와 최단거리인 노드 반환
        visited[now] = True        # 해당 노드 방문처리
        # 해당 노드의 인접한 노드들 간의 거리 계산
        for next in graph[now]:
            cost = distance[now] + next[1]  # 시작->now 거리 + now->now의 인접노드 거리
            if cost < distance[next[0]]:    # cost < 시작->now의 인접노드 다이렉트 거리
                distance[next[0]] = cost


dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF:
        print('도달 할 수 없음')
    else:
        print(distance[i])

좋아요공감
공유하기글 요소

りゅうすいアルゴリズム

特長

アクション

for k in range(n):
  for i in range(n):
      for j in range(n):
          graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

インプリメンテーション

  for k in range(n):
  	for i in range(n):
      for j in range(n):
          arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j])
          ```

コード#コード#

import sys

INF = int(1e9)
n = int(input())
m = int(input())
# 2차원 거리테이블 리스트 초기화
graph = [[INF] * (n+1) for _ in range(n+1)]
# 자신의 노드간의 거리는 0으로 변경
for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            graph[i][j] = 0
# 주어지는 그래프 정보 입력
for _ in range(m):
    # a -> b로 가는 비용은 c
    a, b, c = map(int, input().split())
    graph[a][b] = c

# k=거쳐가는 노드
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

for i in range(1, n+1):
    for j in range(1, n+1):
        if graph[i][j] == INF:
            print('도달할 수 없음', end=' ')
        else:
            print(graph[i][j], end=' ')
    print()

ベルマンフォードアルゴリズム

特長

アクション

コード#コード#

INF = float('inf')
V, E = map(int, input().split())
edges = []
for _ in range(E):
    s, d, w = map(int, input().split())
    edges.append((s, d, w))
def bellman-ford(start):
    dist = [INF] * (V + 1)
    dist[start] = 0
    for i in range(V): 
        for s, d, w in edges:
            if dist[s] != INF and dist[d] > dist[s] + w:
                if i == V - 1: # i가 v-1이면 v번째 간선 추가이므로 음수 사이클
                    return -1
                dist[d] = dist[s] + w
    return dist    
 
print(bellman-ford(0))