最短路の問題

アルゴリズムとデータ構造 アルゴリズムとデータ構造 アルゴリズムとデータ構造 アルゴリズムとデータ構造

2012 2012 年 年 7 7 月 月 17 17 日 日

酒居敬一 酒居敬一

http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2012/index.html http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2012/index.html

1

最短路の問題

（２６０ページ）

• 最短路問題

– グラフの２頂点間を結ぶ道のうちで辺の重みの 和が最小のものを求める問題。

• 対象は辺に重みのついた有向グラフ

• 問題は大きく２種類ある

1. 出発点を１つに固定して、そこから他のすべて の頂点への最短路を求める。

2. すべての２頂点の組み合わせに対して、最短路 を求める。

•

１の方法をすべての頂点に適用するのが最善。

図４

１　アルゴリズムの動き

Ｃ

Ｄ

Ｆ

Ｅ Ａ

６

３

４ ３

２

１

６

単一出発点の問題

（２６１ページ）

• Ｄｉｊｋｓｔｒａのアルゴリズム

– 各頂点への最短路を出発点に近いところか らひとつづつ確定する。

１０

６ ９

７

４

最小の距離を持つ頂点は確定。

他から来るにしても重みが負の 経路がなければ、距離は減らない。

１０ ６

７ ４

Ａ

８

出発点

確定した頂点から行くことのできる 頂点への距離を計算。

3

public class WeightedNode<E> { private E value; //

頂点の値

private Map<WeightedNode<E>, Integer> edges; //

　有向辺

private int distance;

public WeightedNode(E value, Map<WeightedNode<E>, Integer> edges) { this.value = value;

this.edges = edges;

reset();

}

public void reset(){

this.visited = false;

this.distance = Integer.MAX_VALUE;

this.edges.clear();

}

public E getValue() { //

頂点の値を得る。

return value;

}

public Map<WeightedNode<E>, Integer> getEdges(){

return this.edges;

}

//

アクセッサは、このスライドでは省略した。実際には存在する。

public void connectTo(WeightedNode<E> to, int weight){

this.edges.put(to, weight); //

有向辺を追加

} ₄

辺に重みを持たせるため、Ｍａｐを使う。

辺の重み

出発点からの距離

本日使う頂点のデータ構造

public class Dijkstra {

public static <E> void search(Collection<WeightedNode<E>> graph, WeightedNode<E> start){

Set<WeightedNode<E>> visited = new HashSet<WeightedNode<E>>();

Set<WeightedNode<E>> unreached = new HashSet<WeightedNode<E>>(graph);

start.setDistance(0);

while( !unreached.isEmpty() ){

int min_distance = Integer.MAX_VALUE;

WeightedNode<E> min_node = null;

for(WeightedNode<E> node: unreached){

if(node.getDistance() < min_distance){

min_distance = node.getDistance();

min_node = node;

} }

unreached.remove(min_node);

visited.add(min_node);

for(Map.Entry<WeightedNode<E>,Integer> edge: min_node.getEdges().entrySet()){

if(unreached.contains(edge.getKey())){

edge.getKey().setDistance(

Math.min(edge.getKey().getDistance(),

min_node.getDistance() + edge.getValue()));

} } } }

} ₅

集合Ｕ

教科書２６３ページの擬似プログラムをＪａｖａで実装

集合Ｖ

集合Ｕから最小の距離をもつ頂点を探索

private static WeightedNode<Character> nodeA = new WeightedNode<Character>('A', new HashMap<WeightedNode<Character>, Integer>());

private static WeightedNode<Character> nodeB = new WeightedNode<Character>('B', new HashMap<WeightedNode<Character>, Integer>());

private static WeightedNode<Character> nodeC = new WeightedNode<Character>('C', new HashMap<WeightedNode<Character>, Integer>());

private static WeightedNode<Character> nodeD = new WeightedNode<Character>('D', new HashMap<WeightedNode<Character>, Integer>());

private static WeightedNode<Character> nodeE = new WeightedNode<Character>('E', new HashMap<WeightedNode<Character>, Integer>());

private static WeightedNode<Character> nodeF = new WeightedNode<Character>('F', new HashMap<WeightedNode<Character>, Integer>());

private static Collection<WeightedNode<Character>> test_data = new LinkedList<WeightedNode<Character>>();

static {

test_data.add(nodeA);

test_data.add(nodeB);

test_data.add(nodeC);

test_data.add(nodeD);

test_data.add(nodeE);

test_data.add(nodeF);

}

public static void main(String[] args) { System.out.println("図4.5.1");

for(WeightedNode<Character> node: test_data){

node.reset();

}

nodeA.connectTo(nodeB, 6);

nodeA.connectTo(nodeC, 4);

nodeB.connectTo(nodeD, 3);

nodeC.connectTo(nodeE, 3);

nodeC.connectTo(nodeF, 6);

nodeE.connectTo(nodeB, 2);

nodeE.connectTo(nodeD, 1);

search(test_data, nodeA);

System.out.println("頂点" + nodeA.getValue() + "からの距離");

for(WeightedNode<Character> node: test_data){

System.out.println("頂点" + node.getValue() + ": " + node.getDistance());

} }

6

図 4.5.1

頂点 A からの距離 頂点

頂点

頂点

頂点

頂点

頂点

ひとつずつ確定する作戦の前提として、

辺の重みは正の値である。



２６３ページの実装では、集合Ｕから最小の距離をもつ 　頂点を線形探索し、集合Ｕから移動していた。



そもそも、線形探索は時間計算量が多い。



そこで、集合Ｕの替わりにヒープを使うことを考える。



ただし、リストのようなデータ構造でヒープを実装するのは

、

　データ操作に必要な時間計算量の多さから不適切である。



ヒープとしては頂点への参照を入れた配列を使うことにする



最小の距離を持つ頂点をヒープから移動し、ヒープを再構成す 。 る。

実装は省略しますが、２６３ページの擬似プログラムが単純なの で、 それを理解してみるといいだろう。それから２６７ページを理解 する。

7

public class DijkstraArray {

public static <E> void search(WeightedNode<E>[] nodes, int start, int[][] weights){

nodes[start].setDistance(0);

for(int step = 0; step < nodes.length; step++){

int min = Integer.MAX_VALUE;

int p = 0;

for(int x = 0; x < nodes.length; x++){

if( !nodes[x].isVisited() && (nodes[x].getDistance() < min)){

p = x;

min = nodes[x].getDistance();

} }

if(min == Integer.MAX_VALUE){

throw new IllegalArgumentException("

グラフが連結でない。

}

nodes[p].setVisited(true);

for(int x = 0; x < nodes.length; x++){

if(weights[p][x] == Integer.MAX_VALUE){

continue;

}

nodes[x].setDistance(

Math.min(nodes[x].getDistance(),

nodes[p].getDistance() + weights[p][x]));

} } }

}

２６５ページのプログラムのＪａｖａ実装

頂点の配列と、頂点同士の接続行列

private static WeightedNode<Character> nodeA = new WeightedNode<Character>('A');

private static WeightedNode<Character> nodeB = new WeightedNode<Character>('B');

private static WeightedNode<Character> nodeC = new WeightedNode<Character>('C');

private static WeightedNode<Character> nodeD = new WeightedNode<Character>('D');

private static WeightedNode<Character> nodeE = new WeightedNode<Character>('E');

private static WeightedNode<Character> nodeF = new WeightedNode<Character>('F');

@SuppressWarnings("unchecked")

private static WeightedNode<Character>[] test_data = new WeightedNode[] { nodeA, nodeB, nodeC, nodeD, nodeE, nodeF

};

public static void main(String[] args) { System.out.println("図4.5.1");

for(WeightedNode<Character> node: test_data){

node.reset();

}

int[][] weights = new int[test_data.length][test_data.length];

for(int[] from: weights){

for(int i = 0; i < from.length; i++){

from[i] = Integer.MAX_VALUE;

} }

weights[0][1] = 6;

weights[0][2] = 4;

weights[1][3] = 3;

weights[2][4] = 3;

weights[2][5] = 6;

weights[4][1] = 2;

weights[4][3] = 1;

search(test_data, 0, weights);

System.out.println("頂点" + nodeA.getValue() + "からの距離");

for(WeightedNode<Character> node: test_data){

System.out.println("頂点" + node.getValue() + ": " + node.getDistance());

} }

9

図 4.5.1

頂点 A からの距離 頂点

頂点

頂点

頂点

頂点

頂点

これもＤｉｊｋｓｔｒａのアルゴリズムなので、

ひとつずつ確定する作戦の前提として、

辺の重みは正の値である。

全頂点間の問題

（２７０ページ）

• 単一の出発点のアルゴリズムを、全頂点 に 順に適用する方法がひとつ。

• 重み行列が与えられるとき、Ｆｌｏｙｄ の アルゴリズムを使って全頂点間の距離を 求める方法もがある。

10

public class Floyd {

public static <E> void search(int[][] weights, int[][] distances){

for(int i = 0; i < weights.length; i++){

distances[i] = weights[i].clone();

}

for(int k = 0; k < weights.length; k++){

for(int i = 0; i < weights.length; i++){

if(distances[i][k] == Integer.MAX_VALUE){

continue; //

未接続

未計算

for(int j = 0; j < weights[i].length; j++){

if(distances[k][j] == Integer.MAX_VALUE){

continue; //

未接続

未計算

int w = distances[i][k] + distances[k][j];

if(w < distances[i][j]){

distances[i][j] = w;

} } } } } }

11

頂点ｋを経由して、頂点ｉから頂点ｊに至る道があれば、

距離をあらわす行列にその距離を計算し格納する。

２７０ページのプログラム　Ｆｌｏｙｄのアルゴリズム

public static void main(String[] args) { System.out.println("

図

int[][] weights = new int[6][6];

for(int i = 0; i < weights.length; i++){

for(int j = 0; j < weights[i].length; j++){

weights[i][j] = Integer.MAX_VALUE;

}

weights[i][i] = 0;

}

weights[0][1] = 6;

weights[0][2] = 4;

weights[1][3] = 3;

weights[2][4] = 3;

weights[2][5] = 6;

weights[4][1] = 2;

weights[4][3] = 1;

int[][] distances = new int[weights.length][];

search(weights, distances);

System.out.println("

頂点間の距離

for(int i = 0; i < distances.length; i++){

for(int j = 0; j < distances[i].length; j++){

if(distances[i][j] == Integer.MAX_VALUE){

System.out.print("- ");

} else {

System.out.print(distances[i][j] + " ");

} }

System.out.println();

}

} 12

図 4.5.1

頂点間の距離

13



 

false j true

i

a[ , ] （頂点ｉからｊへの道が存在する場合）

（頂点ｉからｊへの道が存在しない場合）

グラフの推移的閉包

（２７５ページ）

グラフの推移的閉包とは、次のような行列ａのことである。

Ｆｌｏｙｄのアルゴリズムとほぼ同じで、

相違点は２頂点間の距離を求めるのではなく、

単に道があるかないかだけを調べる。

そのアルゴリズムをＷａｒｓｈａｌｌのアルゴリズムと呼ぶ。

public class Warshall {

public static <E> void search(boolean[][] adjacency, boolean[][] reachable){

for(int i = 0; i < adjacency.length; i++){

reachable[i] = adjacency[i].clone();

}

for(int k = 0; k < adjacency.length; k++){

for(int i = 0; i < adjacency.length; i++){

if( !reachable[i][k] ){

continue;

}

for(int j = 0; j < adjacency[i].length; j++){

reachable[i][j] = reachable[i][j] || reachable[k][j];

} } } } }

14

入力は隣接行列

出力は推移的閉包

public static void main(String[] args) { System.out.println("

図

boolean[][] adjacency = new boolean[6][6];

for(int i = 0; i < adjacency.length; i++){

for(int j = 0; j < adjacency[i].length; j++){

adjacency[i][j] = false;

}

adjacency[i][i] = true;

}

adjacency[0][1] = true;

adjacency[0][2] = true;

adjacency[1][3] = true;

adjacency[2][4] = true;

adjacency[2][5] = true;

adjacency[4][1] = true;

adjacency[4][3] = true;

boolean[][] reachable = new boolean[adjacency.length][];

search(adjacency, reachable);

System.out.println("

推移的閉包

for(int i = 0; i < reachable.length; i++){

for(int j = 0; j < reachable[i].length; j++){

if(reachable[i][j]){

System.out.print("+ ");

} else {

System.out.print("- ");

} }

System.out.println();

}

} 15

図 4.5.1

推移的閉包

+ + + + + + - + - + - -

- + + + + + - - - + - -

- + - + + - - - - +

期末試験

• 教室 : Ｃ１０１　（いつものＡ１０７は使えませ ん）

• 日時 : ２０１２年７月３０日１６時３０分～１８ 時００分

– 入室限度 : １６時５０分まで – 退出可能 : １７時００分より

• 持ち込み可

– 教科書・資料 ( 自筆・コピー問わず ) は持ち込み可 – 人間・パソコン・携帯電話・ PHS など持ち込み不可

• 学生証必携

– 持っていない場合は教務で発行してもらうこと