가장 짧 은 경 로 를 구 하 는 세 가지 알고리즘: Ford, Dijkstra 와 Floyd

벨 맨 - 포드 알고리즘
Bellman - ford 는 이해 하기 쉬 운 단원 최 단 경로 알고리즘 으로 Bellman - ford 알고리즘 은 두 개의 배열 이 보조 해 야 합 니 다.

dis[i]: 정점 i 에서 원점 까지 최 단 경 로 를 알 고 있 습 니 다

path[i]: 정점 i 를 원점 에서 알 고 있 는 가장 짧 은 경로 에 저장 하고 i 의 앞 정점.

그림 에 n 개의 정점 이 있 으 면 그림 에서 가장 길 고 간단 한 경로 의 길이 가 n - 1 을 초과 하지 않 기 때문에 Ford 알고리즘 은 n - 1 차 교체 로 최 단 경 로 를 확보 합 니 다.
Ford 알고리즘 은 매번 모든 변 을 반복 하고 변 을 이완 (relax) 합 니 다. 변 e 를 이완 시 키 는 것 은 원점 에서 e. start 를 통 해 e. stop 에 도착 하 는 경로 가 가장 짧 은 경로 보다 길 면 가장 짧 은 경 로 를 업데이트 하 는 것 을 말 합 니 다.
설명 하기 편리 하도록 본 고 는 python 실현 알고리즘 을 사용 합 니 다. 먼저 두 개의 도구 함 수 를 실현 합 니 다.

INF = 1e6

def make_mat(m, n, fill=None):
    mat = []
    for i in range(m):
        mat.append([fill] * n)
    return mat

def get_edges(graph):
    n = len(graph)
    edges = []
    for i in range(n):
        for j in range(n):
            if graph[i][j] != 0:
                edges.append((i, j, graph[i][j]))
    return edges

make_mat 2 차원 배열 을 초기 화 하 는 데 사 용 됩 니 다. get_edges 그림 을 인접 행렬 에서 변 경 된 목록 으로 표시 하 는 데 사 용 됩 니 다.
다음은 Bellman - ford 알고리즘 을 실현 할 수 있 습 니 다.

def ford(graph, v0):
    n = len(graph)
    edges = get_edges(graph)
    dis = [INF] * n
    dis[v0] = 0
    path = [0] * n

    for k in range(n-1):
        for edge in edges:
            # relax
            if dis[edge[0]] + edge[2] < dis[edge[1]]:
                dis[edge[1]] = dis[edge[0]] + edge[2]
                path[edge[1]] = edge[0]
   return dis, path

초기 화 후 교체 와 이완 작업 을 수행 하 는 것 은 매우 간단 합 니 다.
path [i] 에서 가장 짧 은 경로 의 전구 정점 을 얻 고 정점 i 에서 원점 까지 의 가장 짧 은 경 로 를 차례로 교체 합 니 다. 거꾸로 하면 원점 에서 i 까지 의 가장 짧 은 경 로 를 얻 을 수 있 습 니 다.

def show(path, start, stop):
    i = stop
    tmp = [stop]
    while i != start:
        i = path[i]
        tmp.append(i)
    return list(reversed(tmp))

Ford 알고리즘 은 경로 의 값 을 마이너스 로 허용 합 니 다. 그러나 경로 에 총 값 이 마이너스 인 링 이 존재 하면 이 링 을 통과 할 때마다 가장 짧 은 경로 의 길이 가 줄 어 듭 니 다. 따라서 그림 의 일부 점 은 가장 짧 은 경로 (최 단 경로 의 길 이 는 마이너스 무한) 가 존재 하지 않 습 니 다.
만약 경로 에 마이너스 고리 가 존재 하지 않 는 다 면 n - 1 차 교체 후 느슨 해 질 수 있 는 변 이 존재 하지 않 습 니 다. 따라서 한 번 더 사 이 드 를 옮 겨 다 니 며 느슨 해 질 수 있 는 변 설명 그림 에 마이너스 고리 가 존재 합 니 다.
이렇게 개선 하면 네 거 티 브 링 을 감지 할 수 있 는 Ford 알고리즘 을 얻 을 수 있 습 니 다.

def ford(graph, v0):
    n = len(graph)
    edges = get_edges(graph)
    dis = [INF] * n
    dis[v0] = 0
    path = [0] * n

    for k in range(n-1):
        for edge in edges:
            # relax
            if dis[edge[0]] + edge[2] < dis[edge[1]]:
                dis[edge[1]] = dis[edge[0]] + edge[2]
                path[edge[1]] = edge[0]

    # check negative loop
    flag = False
    for edge in edges:
        # try to relax
        if dis[edge[0]] + edge[2] < dis[edge[1]]:
            flag = True
            break
    if flag:
        return False
    return dis, path

전체 python 코드

Dijkstra 알고리즘
Dijkstra 알고리즘 은 욕심 산법 이지 만 전체 국면 에서 가장 좋 은 해 를 구 할 수 있 습 니 다. Dijkstra 알고리즘 은 Ford 알고리즘 과 같은 두 개의 보조 배열 이 필요 합 니 다.

dis[i]: 정점 i 에서 원점 까지 최 단 경 로 를 알 고 있 습 니 다

path[i]: 정점 i 를 원점 에서 알 고 있 는 가장 짧 은 경로 에 저장 하고 i 의 앞 정점.

Dijkstra 알고리즘 의 핵심 은 여전히 느슨 한 조작 이지 만 느슨 한 변 을 선택 하 는 방법 은 다르다. Dijkstra 알고리즘 은 방문 되 지 않 은 모든 변 을 작은 지붕 으로 저장 한 다음 에 그 중에서 가장 작은 것 을 선택 하여 느슨 하 게 한다.

def dijkstra(graph, v0):
    n = len(graph)
    dis = [INF] * n
    dis[v0] = 0
    path = [0] * n

    unvisited = get_edges(graph)
    heapq.heapify(unvisited)

    while len(unvisited):
        u = heapq.heappop(unvisited)[1]
        for v in range(len(graph[u])):
            w = graph[u][v]
            if dis[u] + w < dis[v]:
                dis[v] = dis[u] + w
                path[v] = u

    return dis, path

전체 python 코드

Floyd
floyd 알고리즘 은 동적 계획 사상의 다 원 최 단 경로 알고리즘 을 사용 합 니 다. 똑 같이 두 개의 보조 배열 이 필요 하지만 다 원 최 단 경로 알고리즘 으로서 그 구조 가 다 릅 니 다.

dis[i][j]: 정점 i 에서 정점 j 까지 알려 진 최 단 경 로 를 저장 하고 직접 연결 로 초기 화 합 니 다

path[i][j]: 정점 i 에서 정점 j 까지 알려 진 가장 짧 은 경 로 를 저장 하고 j

로 초기 화 합 니 다.

def floyd(graph):
    # init
    m = len(graph)
    dis = make_mat(m, m, fill=0)
    path = make_mat(m, m, fill=0)
    for i in range(m):
        for j in range(m):
            dis[i][j] = graph[i][j]
            path[i][j] = j

    for k in range(m):
        for i in range(m):
            for j in range(m):
                # relax
                if dis[i][k] + dis[k][j] < dis[i][j]:
                    dis[i][j] = dis[i][k] + dis[k][j]
                    path[i][j] = path[i][k]

    return dis, path

알고리즘 핵심 은 정점 k, i, j 를 옮 겨 다 니 는 것 입 니 다. 정점 i 에서 정점 k 를 거 쳐 정점 j 에 도착 하 는 경 로 는 이미 알 고 있 는 i 에서 j 까지 의 최 단 경로 보다 짧 으 면 이미 알 고 있 는 최 단 경 로 를 업데이트 합 니 다.

전체 python 코드