[파이썬] 두 노드 사이의 노드 찾기

예제 코드를 기반으로 알 수 있듯이 귀하의 shortestPath방법과 예제 코드에서 사용하는 방법이 동일한 결과를 반환 한다고 생각하지 않습니다 . 나는 그것이 다음과 같은 것을 반환한다고 생각한다.

({'E': 4.0, 'D': 3.0, 'A': 0, 'C': 5.0, 'B': 1.0}, {'B': 'A', 'D': 'B', 'C': 'A', 'E':'D', 'A': None})

따라서 최종 거리뿐만 아니라 각 노드와 그 앞에있는 노드도 포함됩니다 (시작 노드를 포함할지 여부는 모르겠습니다).

shortestPath메서드 에서 생성 할 수 있다면 기본 for루프 만 사용하도록 예제 코드를 변경하는 것이 너무 어렵지 않아야합니다 . 한 가지 가능성이 있습니다.

final_distances,predecessors = ShortestPath(graph,start)
path = end
while end != start:
    end = predecessors[end]
        path = '%s->%s' % (end, path)
        return path
        

결과를 목록에 저장하고 각 새 노드를 해당 목록의 끝에 추가하는 대신 매번 앞에 추가하는 문자열을 쉽게 만들 수 있습니다. 반환해야하는 경우 목록으로 비슷한 작업을 수행 할 수 있습니다.

final_distances,predecessors = ShortestPath(graph,start)
path = [end]
while end != start:
    end = predecessors[end]
        path = [end] + path
        return path
        

여기서 나는를 포함하는 목록이되도록 경로를 초기화하고 있으며 end루프의 각 단계에서 현재 노드의 선행자를 찾아 경로 앞에 추가합니다.

출처
https://stackoverflow.com/questions/22079851