선형 최단 경로 알고리즘이 왜 무향 순환 그래프에 대해 작동하지 않습니까?

Question

저는 파이썬에서 구현 된 기본적인 선형 최단 경로 알고리즘을 가지고 있습니다. 다양한 사이트에 따르면, 이것은 this, this 및 this을 비롯한 지시 된 비순환 적 그래프에서만 작동합니다. 그러나 이것이 왜 그런지 나는 알지 못합니다.

나는주기와 무향 가장자리가있는 그래프에 대해 알고리즘을 테스트 해 보았지만 정상적으로 작동했습니다.

질문 : 왜 선형 최단 경로 알고리즘이 비 방향성 순환 그래프에서 작동하지 않습니까? 사이드 질문, 이 알고리즘의 이름은 무엇입니까? 참고로

, 여기에 내가 알고리즘에 대해 쓴 코드는 다음과 같습니다 베타에 의해 요청으로, 여기에 위상 일종이다 :

def shortestPath(start, end, graph): 
    # First, topologically sort the graph, to determine which order to traverse it in 
    sorted = toplogicalSort(start, graph) 

    # Get ready to store the current weight of each node's path, and their predecessor 
    weights = [0] + [float('inf')] * (len(graph) - 1) 
    predecessor = [0] * len(graph) 

    # Next, relaxes all edges in the order of sorted nodes 
    for node in sorted: 
     for neighbour in graph[node]: 

      # Checks if it would be cheaper to take this path, as opposed to the last path 
      if weights[neighbour[0]] > weights[node] + neighbour[1]: 

       # If it is, then adjust the weight and predecessor 
       weights[neighbour[0]] = weights[node] + neighbour[1] 
       predecessor[neighbour[0]] = node 

    # Returns the shortest path to the end 
    path = [end] 
    while path[len(path) - 1] != start: 
     path.append(predecessor[path[len(path) - 1]]) 
    return path[::-1] 

편집

# Toplogically sorts the graph given, starting from the start point given. 
def toplogicalSort(start, graph): 
    # Runs a DFS on all nodes connected to the starting node in the graph 
    def DFS(start): 
     for node in graph[start]: 
      if not node[0] in checked: 
       checked[node[0]] = True 
       DFS(node[0]) 
     finish.append(start) 

    # Stores the finish point of all nodes in the graph, and a boolean stating if they have been checked 
    finish, checked = [], {} 
    DFS(start) 

    # Reverses the order of the sort, to get a proper topology; then returns 
    return finish[::-1] 

Answer 1

때문에 당신은 할 수 없습니다 순환으로 그래프를 토폴로지별로 정렬합니다. 따라서 어떤 노드가 다른 노드보다 먼저 나오는지 알 수 없으므로 방향이없는 그래프도 문제가되지 않습니다.

편집 : 의견을 읽은 후에는 실제로 그것이 @ 베타의 의미라고 생각합니다.

Answer 2

주기가있을 때 토폴로지 정렬은 최단 경로의 올바른 순서를 보장 할 수 없습니다. 그것은 비록

A->B->C->D 

:

A->C->B->D 

그러나 위상 종류의 주문을 생성 할 수 있습니다

A->C, A->B, B->C, C->B, B->D 

올바른 최단 경로는 말 : 예를 들어

, 우리는 그래프를 C을 방문 할 때 B을 올바른 순서로 업데이트하지만 B은 다시 방문하지 않으므로 D에 정확한 무게를 전파 할 수 없습니다. 그러나 경로는 정확합니다.