2 섹션 질문에 문제가 있습니다.그래프의 최단 경로
G = (V, E)는 비가 중 그래프입니다. t, s는 그래프의 노드입니다. e = (a, b)는 그래프의 가장자리입니다.
1) E가 행의 t에서 모든 최단 경로의 일부인지를 확인 효율적인 알고리즘을 제안.
2) E 는 행의 t 최단 경로 하나의 일부인지를 확인 효율적인 알고리즘을 제안.
섹션 1을 해결하기위한 포럼 제안에서 Dijkstra 알고리즘을 두 번 사용했습니다. 한 번만 주어진 가장자리와 한 번 사용하지 않고 나타났습니다. 그런 다음 결과를 비교해야합니다. 그러나 섹션 2를 해결하는보다 효율적인 방법을 생각해 내지 못했습니다. 가능하다고 생각하지만 어떻게해야할지 모르겠습니다.
제안 사항?
실제로 가중치가없고 방향이없는 그래프의 경우 Dijkstra를 사용할 필요가 없으며 간단한 BFS는 목적으로 사용됩니다.
컴퓨팅 내지 e의 최단 경로 (E)로부터의 최단 경로는 경우
의해 t : e는 t하는 들로부터이어야 하나 개 최단 경로의 일부인지 여부에있어서의 검사에 이어
이 두 경로 길이의 합은 s에서 t까지의 최단 경로와 같으며, e는 s에서 t까지의 최단 경로 중 가장 짧은 경로의 일부입니다. 당신은 전자가 의 일부인지 여부를 알고 싶은 경우에
s -----> e -------> t
정확히 s의 최단 경로을 t 하나, 다음뿐만 아니라, 다음 링크는 어쩌면 도움이 될. 그것은 방향성 그래프에 관한 것이지만, 우리의 undirected 그래프는 u to v과 v to u의 가장자리를 가진 유향 그래프로 생각할 수 있습니다. 2이어야
문제 익스트라 알고리즘 하나 (수정) 패스를 사용하여 풀 수 있어야한다.
앞에서와 마찬가지로 검색 공간의 경계를 우선 순위 대기열에 두지 만 한 가지 더 많은 정보도 추가합니다.이 정보는 국경의이 부분으로 이어지는 경로가 문제의 가장자리.
s 만 대기열에 있고 플래그는 거짓입니다.e이 통과 할 때마다 (즉, 처음으로 플래그가 참으로 설정됩니다.e을 트래버스하여 v에 도달해야한다면 v을 큐에 넣을 때 플래그를 true로 설정합니다.e 대상이 t이 스택에서 팝되면 플래그가 true로 설정됩니다.