最短経路網の性質とその高速探索アルゴリズム

情報処理学会

書誌事項

タイトル別名
  • Attributes of Shortest Path Network and the Fast Algorithm for Betweenness Centrality

説明

単連結なそう方向グラフにおいて、特定のノードを終点とし、グラフ内の任意のノードから、その終点ノードへ最短経路からなる部分グラフを、その終点ノードへ最短経路網と呼ぶ。この計算には、ダイクストラのSSSPアルゴリズムが知られている。この論文では、この最短経路網の性質をいくつか示し、それを用いることによって、すでに計算済みの、あるノードへの最短経路網から、そのノードに隣接しているほかのノードへの最短経路網を求めるアルゴリズムを提案する。このアルゴリズムは、単に直接SSSPを用いて目的の最短経路網求めるより高速であることを示す。

In connected undirected graph G =< N, V >, we call Go as “shortest path graph of o” which is collection of shortest paths to o form any node n in G. Dijkstra’s SSSP algorithm can make a Go in O(|V |). In this paper, we show some attributes in shortest path graph, and introduce a new algorithm which make Gs from Go , where s is neighbor node of o. And show our new algorithm is faster then Dijkstra’s algorithm.

収録刊行物

詳細情報 詳細情報について

問題の指摘

ページトップへ