최단 경로 알고리즘 : 여러 소스, 가장 가까운 대상

Question

그래프의 단일 시작점부터 다른 모든 정점까지의 최단 경로를 찾기 위해 Bellman-Ford 알고리즘 및 Dijkstra 알고리즘과 같은 알고리즘이 있습니다. 이들의 다중 소스 버전은 모든 에지를 반전시키고 목적지를 시작 노드로 취급함으로써 달성 될 수있다.

내가 그래프의 소스의 "중심 (barycentre)"를 찾아 그 연장하고자하는 "합의"를 "공정"경로를 찾는 소스의 설정을 "가장 가까운"입니다 즉 정점 꼭지점.

이미 알고리즘을 제공하는 알고리즘이 있습니까? 그들은 무엇인가?

Answer 1

Floyd–Warshall algorithm

난 당신이 의 "그래프 편심을"계산하려는 생각 소스 (S1, S2, ... SN-1, 주석).

1. 그래프에서 최단 경로의 모든 쌍을 계산하려면 Floyd-Warshall 알고리즘을 사용하십시오.
2. (d [v, S1] + d [v, S2] + d [v, S3] .... d [v, Sn-1]의 최소 합계 인 그래프에서 결과 노드 V를 찾는다. + D [V, 주석])

정보 :

Graph Eccentricity

UPDATE

아마 거리 그래프 G (V, E)에서, 존재하는 노드 V 찾는 에 S은 모두 동일합니다 현실 주의자가 아닙니다. ic. d (v, Sn), d [v, Sn] 사이의 (d [v, S1], d [ 범위는 0보다 크거나 같고 선택한 특정 값 미만입니다.