최단 경로 알고리즘: 다중 소스, 가장 가까운 목적지 (Shortest-path algorithm: multiple source, closest destination)

문제 설명

최단 경로 알고리즘: 다중 소스, 가장 가까운 목적지 (Shortest‑path algorithm: multiple source, closest destination)

Bellman‑Ford 알고리즘 및 Dijkstra 알고리즘과 같은 알고리즘은 그래프의 단일 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾기 위해 존재합니다. 그들의 다중 소스 버전은 모든 에지를 역전시키고 목적지를 시작 노드로 처리하여 달성할 수 있습니다.

그래프에서 소스의 "중심점", 즉 즉 소스 세트에 "가장 가까운" 정점을 찾기 위해 확장하고 싶습니다. "합의된" 정점에 대한 공정한" 경로.

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

참조 솔루션

방법 1:

Floyd–Warshall algorithm

I think you want to calculate the "Graph Eccentricity" of the sources (S1,S2,...Sn‑1,Sn).

1. Use Floyd‑Warshall algorithm to calculate All Pair of Shortest Path in graph.
2. Find the result node V in graph, which is the min sum of (d[v,S1]+d[v,S2]+d[v,S3]....d[v,Sn‑1]+d[v,Sn])

More Information:

Graph Eccentricity

UPDATE

Maybe finding an existed node v In Graph G(V,E) which the distance to S are all equal is not realistic. You can calculate the Stand Deviation of (d[v,S1],d[v,S2],d[v,S3]....d[v,Sn‑1],d[v,Sn]) between a range that grater or equal than 0 and less than a certain value you choose.

(by Alban Dericbourg、shawn)

참조 문서

1. Shortest‑path algorithm: multiple source, closest destination (CC BY‑SA 2.5/3.0/4.0)