다익스트라, 플로이드와샬, 벨만포드에 대해서!

 

가중치가 있는 그래프탐색!

---

 

 

다익스트라 — 시작점과 다른 모든 정점간의 최단경로를 탐색할때 사용

---

시작점부터 탐색하여 연결되는 정점의 거리를 최솟값으로 최신화 해주고

시작정점으로 부터 연결된 정점까지의 거리중 최솟값을 가지고 아직 방문하지않은 정점으로 이동하여 반복해줍니다.

# 방문하지 않은 노드이면서 시작노드와 최단거리인 노드 반환
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      #cost(원래값)보다 작을때 최신화

[알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm)

[알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm)

 

ex) 소방차 문제

[알고스팟][C++] FIRETRUCKS: 소방차

[알고스팟][C++] FIRETRUCKS: 소방차

[백준] 1753번 최단경로 파이썬 해설 (다익스트라 알고리즘)

[백준] 1753번 최단경로 파이썬 해설 (다익스트라 알고리즘)

---

 

 

플로이드 와샬 — 모든정점간의 최단거리를 계산하여 나타냄-음수간선도 가능!

# k : 경유지
for k in range(1, v+1):
    # i : 출발지    
    for i in range(1, v+1):
        # j : 목적지
        for j in range(1, v+1):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
						#바로가는거하고 교차해서가는거 비교

for i in range(V):
        if dist[i][i] < 0:
            # 자기자신의 경로길이가 음수면 음수 사이클 검출
            return -1

 

 

한 정점을 경유지로 정해놓고 경로를 탐색한후 최솟값으로 최신화

알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘

알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘

 

 

ex) 배달

코딩테스트 연습 - 배달

코딩테스트 연습 - 배달

주로 다익스트라와 플로이드알고리즘이 탐색에 사용됨

---

벨만 포드 — 음수 간선이 있는 경우에서 시작 정점으로부터 다른 정점까지의 최단 경로를 구하기 위해 사용( 많이안쓰이는듯)——→> 음수간선이 있는 다익스트라문제?

def bellman_ford(graph, start):
    distance, predecessor = dict(), dict()  # 거리 값, 각 정점의 이전 정점을 저장할 딕셔너리
    # 거리 값을 모두 무한대로 초기화 / 이전 정점은 None으로 초기화
    for node in graph:  
        distance[node], predecessor[node] = float('inf'), None
    distance[start] = 0  # 시작 정점 거리는 0

    # 간선 개수(V-1)만큼 반복
    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbour in graph[node]:  # 각 정점마다 모든 인접 정점들을 탐색
                # (기존 인접 정점까지의 거리 > 기존 현재 정점까지 거리 + 현재 정점부터 인접 정점까지 거리)인 경우 갱신
                if distance[neighbour] > distance[node] + graph[node][neighbour]:
                    distance[neighbour] = distance[node] + graph[node][neighbour]
                    predecessor[neighbour] = node

    for node in graph:
        for neighbour in graph[node]:
            if distance[neighbour] > distance[node] + graph[node][neighbour]:
                return -1, 

    return distance, predecessor

—> 주의 음수 사이클 발생시 값이 계속작아져 무한루프를 돌수도있기에 사이클 존재 검사 해야함!

---

 

 

플로이드, 다익스트라, 벨만---> 다른블로그도 있어서 찾아봤습니다!

 

 

https://codedoc.tistory.com/95

플로이드, 다익스트라 알고리즘 비교

[알고리즘] 최단 경로 알고리즘 - 다익스트라, 벨만 포드 ,플로이드 알고리즘

[알고리즘] 최단 경로 알고리즘 - 다익스트라, 벨만 포드 ,플로이드 알고리즘

 

 

 

틀린점이 있다면 댓 달아주세요!