원형이면서 방향이없고 가중치가없는 순환 그래프의 최단 경로

Question

원형 네트워크가 있으며 각 노드가 가장 가까운 이웃 노드에 연결되어 있습니다. 나는 장거리 연결을 일정량 추가하고, 더 긴 연결은 상당히 덜 가능성이있다.

It can be represented like this

and it is stored in a 2D array like this

나는 무작위로 두 개의 노드를 선택하고 그들 사이의 최단 경로를 찾는 루틴을 만들고 싶습니다

. 이것을 달성하기위한 가장 효과적인 알고리즘은 무엇입니까?

Answer 1

Dijkstra의 알고리즘이라고 불리는 잘 알려진 알고리즘이 있습니다.

프림의 알고리즘 최소 스패닝 트리를 구성한다 -이 :/프리즘 w 및 익스트라에 관한 b를 지금까지 차이로 - : 나는 그래프가 무엇인지 알고 도착하기 전에 나는

가 명확 위해 편집 ... 그 이름을 들었습니다 이 그래프는 그래프의 모든 노드를 연결하고 모든 노드를 연결하는 모든 트리 중에서 총 비용이 가장 적은 트리입니다. 그러나 MST의 두 노드 사이의 경로 길이는 원래 그래프의 두 노드 사이의 최단 경로가 아닐 수 있습니다.

Dijkstra의 알고리즘은 일부 소스 노드에서 시작하는 최단 경로 트리를 구성합니다. 최단 경로 트리는 그래프의 모든 노드를 연결하고 그래프의 일부 시작 노드에서 다른 노드까지의 경로 길이를 최소화하는 트리입니다.

그래서 최단 경로가 두 노드 사이에 있으면 Dijkstra 's가 중요합니다. 나는 다른 옵션에 대해 많이 알지 못한다.하지만 Kruskal은 Prim과 같은 라인에있는 drwan이다.