Manoj Gupta, 1996년부터 이어진 최단 경로 알고리즘 한계 넘었다

인도공과대학 간디나가르(IIT Gandhinagar)의 Manoj Gupta가 1996년부터 컴퓨터 과학계를 가로막던 한계를 극복했습니다. 그가 개발한 알고리즘은 거대한 네트워크에서 두 지점 사이의 최단 거리를 계산 시간 증가 없이 더 정확하게 추정할 수 있습니다.

모든 쌍 최단 경로 문제

네트워크는 관계로 연결된 점들의 집합입니다. 점은 도시, 컴퓨터, 기차역은 물론 뉴런이나 생물학적 구조의 요소를 나타낼 수도 있습니다. 내비게이션 앱, 교통 시스템, 인터넷 인프라가 날마다 이런 계산을 수행합니다. 하지만 거대한 네트워크에서 가능한 모든 쌍의 거리를 구해야 하면 문제가 훨씬 복잡해집니다. 이를 APSP(All-Pairs Shortest Paths)라고 부릅니다.

촘촘하게 연결된 대규모 네트워크에서 정확한 거리를 모두 구하려면 막대한 연산 자원이 필요합니다. 그래서 연구자들은 모든 경로를 분석하지 않고도 신뢰할 만한 결과를 얻는 방법을 찾아 왔습니다. 1996년 Dor, Halperin, Zwick은 추정값이 실제 최단 거리의 두 배를 넘지 않음을 보장하는 알고리즘을 내놓았습니다. 이를 2배 근사라고 합니다.

다단계 샘플링으로 정확도 개선

이 방식에는 약점이 있었습니다. 보장은 주로 멀리 떨어진 지점에서 잘 작동했고, 가까운 지점에서는 오차가 커질 수 있었습니다. 실제 경로가 두 구간인데 추정이 다섯 구간으로 나오면 두 배 허용 범위를 넘게 됩니다.

Gupta는 거리 추정에 쓰는 지점을 고르는 방식을 개선했습니다. 기존에는 비교적 작은 대표 정점 집합에 의존했지만, 새 알고리즘은 다단계 샘플링 전략을 씁니다. 하나의 선택 집합에 기대지 않고 네트워크 구조를 여러 수준에서 분석하는 방식입니다. 덕분에 이전에는 놓칠 수 있던 짧은 연결도 반영합니다.

가장 중요한 점은 정확도를 높이는 데 알고리즘 전체의 계산 복잡도 증가가 필요 없다는 것입니다. 실행 시간을 늘리지 않고도 더 믿을 만한 결과를 얻을 수 있습니다.

이번 성과는 통신, 교통, 소셜 미디어, 인공지능 시스템 등 대규모 네트워크를 분석하는 여러 분야에 의미가 있을 수 있습니다. 구성 요소 간 거리를 빠르고 안정적으로 추정하면 의존 관계 분석과 시스템 전체의 최적화에 도움이 됩니다.