| 1 |
1
최단경로 탐색 장치가 요약 그래프를 기반으로 최단경로를 탐색하는 방법에 있어서,상기 요약 그래프에 대한 보정 리스트를 기반으로 그래프 요약으로 인해 원그래프(original graph)에는 존재하지만 상기 요약 그래프에서는 제거된 에지를 이용하여 상기 요약 그래프를 보정하는 단계;상기 보정된 요약 그래프를 기반으로 소스 노드로부터 목적지 노드까지의 최단경로 후보를 탐색하는 단계; 및상기 그래프 요약으로 인해 상기 원그래프에는 존재하지 않지만 상기 요약 그래프에 추가된 에지 정보를 이용하여 상기 탐색된 최단경로 후보의 유효성을 검사하는 단계를 포함하는 최단경로 탐색 방법
|
| 2 |
2
제1항에 있어서,상기 원그래프는 비가중치 그래프이고, 상기 요약 그래프는 상기 원그래프가 기 설정된 그래프 요약 방법에 의해 요약된 그래프인 것을 특징으로 하는 최단경로 탐색 방법
|
| 3 |
3
제1항에 있어서,상기 보정 리스트는,상기 원그래프에서 제거된 에지에 대한 정보 및 상기 요약 그래프에 추가된 에지 정보를 포함하는 것을 특징으로 하는 최단경로 탐색 방법
|
| 4 |
4
제1항에 있어서,상기 최단경로 후보를 탐색하는 단계는,상기 에지가 구성된 요약 그래프에 대해 너비 우선 탐색을 수행하여 상기 소스 노드로부터 목적지 노드까지의 최단경로 후보를 탐색하는 단계인 것을 특징으로 하는 최단경로 탐색 방법
|
| 5 |
5
제1항에 있어서,상기 소스 노드 및 상기 목적지 노드 중 적어도 하나가 상기 그래프 요약에 의해 요약된 입자 노드인 경우, 해당 노드를 해당 입자 노드를 포함하는 슈퍼 노드로 변경하는 단계를 더 포함하는 것을 특징으로 하는 최단경로 탐색 방법
|
| 6 |
6
제1항에 있어서,상기 최단경로 후보의 유효성을 검사하는 단계는,상기 최단경로 후보에 포함된 슈퍼 노드의 수만큼 수행되는 것을 특징으로 하는 최단경로 탐색 방법
|
| 7 |
7
요약 그래프에 대한 보정 리스트를 기반으로 그래프 요약으로 인해 원그래프(original graph)에는 존재하지만 상기 요약 그래프에는 제거된 에지를 상기 요약 그래프에 구성하는 구성부;상기 에지가 구성된 요약 그래프를 기반으로 소스 노드로부터 목적지 노드까지의 최단경로 후보를 탐색하는 탐색부; 및상기 그래프 요약으로 인해 상기 원그래프에는 존재하지 않지만 상기 요약 그래프에 추가된 에지 정보를 이용하여 상기 탐색된 최단경로 후보의 유효성을 검사하는 검사부를 포함하는 최단경로 탐색 장치
|
| 8 |
8
제7항에 있어서,상기 원그래프는 비가중치 그래프이고, 상기 요약 그래프는 상기 원그래프가 기 설정된 그래프 요약 방법에 의해 요약된 그래프인 것을 특징으로 하는 최단경로 탐색 장치
|
| 9 |
9
제7항에 있어서,상기 보정 리스트는,상기 원그래프에서 제거된 에지에 대한 정보 및 상기 요약 그래프에 추가된 에지 정보를 포함하는 것을 특징으로 하는 최단경로 탐색 장치
|
| 10 |
10
제7항에 있어서,상기 탐색부는,상기 에지가 구성된 요약 그래프에 대해 너비 우선 탐색을 수행하여 상기 소스 노드로부터 목적지 노드까지의 최단경로 후보를 탐색하는 것을 특징으로 하는 최단경로 탐색 장치
|
| 11 |
11
제7항에 있어서,상기 탐색부는,상기 소스 노드 및 상기 목적지 노드 중 적어도 하나가 상기 그래프 요약에 의해 요약된 입자 노드인 경우, 해당 노드를 해당 입자 노드를 포함하는 슈퍼 노드로 변경하는 것을 특징으로 하는 최단경로 탐색 장치
|
| 12 |
12
제7항에 있어서,상기 검사부는,상기 최단경로 후보에 포함된 슈퍼 노드의 수만큼 상기 최단경로 후보에 대해 유효성 검사를 수행하는 것을 특징으로 하는 최단경로 탐색 장치
|
