그래프 순회 알고리즘 최단 경로 Dijkstra 알고리즘

최단 경로 문제는 그래프 이론 연구의 고전적인 알고리즘 문제로, 그래프의 두 노드 또는 단일 노드 사이에서 다른 노드까지의 최단 경로를 찾는 것을 목표로 합니다. 문제에 따라 알고리즘의 특정 형태는 다음과 같습니다.

일반적으로 사용되는 최단 경로 알고리즘에는 Dijkstra 알고리즘, A 알고리즘, Bellman-Ford 알고리즘, SPFA 알고리즘(Bellman-Ford 알고리즘의 개선된 버전)이 포함됩니다. ), Floyd-Warshall 알고리즘, Johnson 알고리즘 및 양방향 BFS 알고리즘. 이 기사에서는 Dijkstra 알고리즘의 원리와 구현에 중점을 둘 것입니다.

Dijkstra 알고리즘 또는 Dijkstra 알고리즘으로 번역되는 Dijkstra 알고리즘은 1956년 네덜란드 컴퓨터 과학자 Edsgel Dijkstra가 유향 그래프의 단일 소스 최단 경로 문제를 해결하기 위해 제안했습니다. 소위 단일 소스 최단 경로 문제는 시작점을 결정하고 그래프에서 해당 노드에서 임의의 노드까지의 최단 경로를 찾는 것을 의미합니다. 이 알고리즘은 두 도시 사이의 최단 경로를 찾거나 유명한 여행 세일즈맨을 해결하는 데 사용될 수 있습니다. 문제.

문제 설명: 무방향 그래프에서 는 그래프 노드의 집합이고 는 노드를 연결하는 간선의 집합입니다. 각 간선의 가중치가 이라고 가정하고 정점에서 나머지 노드까지의 최단 경로(단일 소스 최단 경로)를 찾습니다.

가중치가 부여된 무방향 그래프입니다. 그래프의 정점은 두 그룹으로 나뉩니다. 첫 번째 그룹은 최단 경로가 발견된 정점 집합입니다. 처음에는 소스 포인트만 있습니다. 최단 경로가 발견되면 모든 정점이 추가되고 알고리즘이 종료될 때까지 새로운 정점이 추가됩니다. 두 번째 그룹은 의 정점이 증가함에 따라 의 정점이 점차 감소하는 미결정 최단 경로 정점 집합입니다.

다음 그림을 예로 들어 Dijkstra 알고리즘의 작업 흐름을 보여줍니다(정점을 시작점으로 사용).

참고:

01)은 최단 경로의 정점 집합입니다.

02)는 최단 경로가 계산되지 않은 정점 집합입니다.

03)은 정점으로부터의 최단 거리를 의미합니다. 정점은 3입니다.

1단계: 추가할 정점 선택

2단계: 추가할 정점 선택, 정점 사이의 최단 거리가 업데이트됩니다.

단계 3: 추가할 정점 선택, 정점 간 최단 거리 업데이트

4단계: 정점 선택 및 추가, 정점 간 최단 거리 업데이트

5단계: 꼭지점을 선택하여 추가하고, 꼭지점 사이의 최단 거리를 업데이트합니다.

6단계: 추가할 꼭지점을 선택하고, 업데이트할 꼭지점 사이의 최단 거리를 업데이트합니다.

Step 7: 추가할 정점을 선택하고 업데이트할 정점 사이의 최단 거리를 선택합니다.

예: 노드 번호 1-7은 각각 A,B,C,D,E,F,G를 나타냅니다. p>

(s.paths <- shortest.paths(g, 알고리즘 = "dijkstra")) 출력 결과:

(s .paths <- shortest.paths(g,4, 알고리즘 = "dijkstra")) 출력 결과:

예:

D(4)에서 G(7)까지의 최단 경로 찾기:

[1] Wikipedia, 최단 경로 문제: /yalishadaa/article/details/55827681;

[3]RDocumentation: https://www.rdocumentation.org/packages/RNeo4j/versions/1.6.4/topics/dijkstra ;

[4]RDocumentation: https://www.rdocumentation.org/packages/igraph/versions/0.1.1/topics/shortest.paths ;

[5]Pypi : https://pypi.org/project/Dijkstar/