グラフで遊んでみる

最短経路問題で使われるダイクストラアルゴリズムの復習のために、JavaScriptで簡単なプログラムを作ってみました。

グラフを表す

今回扱う問題は、有向グラフにしておきます。まず、グラフを表すために、ノードとエッジに対応するクラスを作ります。

/**
 * ノード
 * @param {Object} name ユニークな名前にすること
 * @param {Object} edgeList エッジを配列として保持
 */
function Node(name, edgeList) {
	this.name = name;
	if(typeof edgeList == "array") this.edgeList = edgeList;
	else this.edgeList = new Array();
	
	Node.prototype.addLink = function(node, cost) {
		var link = new Edge(this, node, cost);
		this.edgeList.push(link);
	};
	Node.prototype.toString = function() {
		return this.name;
	}
};

/**
 * エッジ
 * @param {Object} from 基のノード
 * @param {Object} to 次のノード
 * @param {Object} cost コスト
 */
function Edge(from, to, cost) {
	if(from) this.from = from;
	if(to) this.to = to;
	if(cost) this.cost = cost;
	else this.cost = 0;

	Edge.prototype.toString = function() {
		return this.from + " - " + this.to + "   " + this.cost;
	};
};

このグラフは、エッジに重みを付けることができます。Edgeのcostという引数が、それに該当します。
次にこれを使って簡単なグラフを作ります。イメージとしては以下のようなわっかの形のグラフになります。

 A - B - C - (A)

上の図には書いていませんが、ノードとノードの間にあるエッジには重みがあります。これを表にしてみると、こんな感じになります。

元のノード	先のノード	重み
A	B	2
B	C	4
C	A	4

上のようなグラフを表現するためのコードは以下の通りです。

var A = new Node("A");
var B = new Node("B");
var C = new Node("C");
A.addLink(B, 2);
B.addLink(C, 4);
C.addLink(A, 4);

探索してみる

探索の例として、あるノードを基点として探索を開始し、全てのノードの、全てのエッジを集めてみましょう。まず最初にノードAだけが与えられているものとします。ここからエッジをたどって各ノードへと進んでいきます。この際、通過したエッジを保存していきます。ノードを順番にたどっていくわけですから、関数の再帰呼び出しを利用します。また、最初のノードに戻ってくることが無いよう、一度探索した場所を保存しておくことも大切です。今回は、一度探索したノードを保存しておきます。これを以下のように実装しました。toListに開始位置のノードを渡してやると、全てのエッジが入った配列が返ってきます。

/**
 * startとgoalはnodeオブジェクト
 * @param {Object} start
 * @param {Object} goal
 */
function toList(start) {
	var list = new Array();
	var finish  = new Array(); //探索終了
	listRec(start, list, finish);
	return list;
};

/**
 * toListから再帰的に呼び出される
 * @param {Object} node
 * @param {Object} list
 * @param {Object} finish
 */
function listRec(node, list, finish) {
	for (var j = 0; j < finish.length; j++) { //すでに登録済みかどうか調べる
		if (node == finish[j]) {
			return; //抜ける
		}
	}
	finish.push(node); //探索済みノードに追加
	for (var i = 0; i < node.edgeList.length; i++) { //エッジをリストに登録
		var edge = node.edgeList[i];
		list.push(edge); //リストに追加
		listRec(edge.to, list, finish)
	}
};

toList関数の使い方は、以下の通りになります。

var list = toList(A);
for (var i = 0; i < list.length; i++) {
	document.write(list[i] + "<br>");
}

これを実行すると、以下のように出力されます。ちなみに、このフォーマットは、EdgeオブジェクトのtoStringメソッドによるものです。

A - B 2
B - C 4
C - A 4

もう少し複雑なグラフ

さすがに上の例は簡単すぎるので、もう少し複雑なグラフを作ります。(グラフ自体の図がなくて、申し訳ありません)

元のノード	先のノード	重み
A	B	1
A	C	2
A	D	1
B	E	4
C	B	1
C	F	2
D	F	2
F	D	3
F	E	3

var A = new Node("A");
var B = new Node("B");
var C = new Node("C");
var D = new Node("D");
var E = new Node("E");
var F = new Node("F");
A.addLink(B, 1);
A.addLink(C, 2);
A.addLink(D, 1);
B.addLink(E, 4);
C.addLink(B, 1);
C.addLink(F, 2);
D.addLink(F, 2);
F.addLink(D, 3);
F.addLink(E, 3);

これを実行すると、以下のように出力されます。

A - B 1
B - E 4
A - C 2
C - B 1
C - F 2
F - D 3
D - F 2
F - E 3
A - D 1

順番がぐちゃぐちゃで分りにくいので、出力する前にソート

var list = toList(A);
list.sort(function(a, b){
    return a.from > b.from ? 1 : -1;
});
for (var i = 0; i < list.length; i++) {
	document.write(list[i] + "<br>");
}

ソート後の出力

A - B 1
A - C 2
A - D 1
B - E 4
C - B 1
C - F 2
D - F 2
F - D 3
F - E 3

ダイクストラアルゴリズム

いよいよダイクストラに取り掛かります。ご存じのとおり、ダイクストラはノードからノードへの最短経路を求めるためのアルゴリズムです。始点となるノードはある1点だけですが、終点となるノードは、探索できる範囲にある全てのノードが対象です。つまり、ある一点から、全ての場所についての最短経路を求めるアルゴリムです。
まず、経路を表すRouteクラスを作っていきます。

/**
 * あるノードからあるノードへの経路を示す
 * @param {Object} from
 * @param {Object} to
 * @param {Object} route　Edgeの配列
 */
function Route(from, to, route) {
	this.from = from;
	this.to = to;
	if(route) this.route = route; //Edgeの集合
	else this.route = new Array();
}

fromが始点ノード、toが終点ノードです。また、このクラスは内部にrouteという配列を持っており、これはプロパティfromから、プロパティtoへと通じる経路になっています。具体的には、routeにはEdgeの集合を入れます。例えば、次のような経路があった場合

A - B - C

元のノード	先のノード	重み
A	B	2
B	C	4

このとき、fromはA、toはC、そしてrouteには次のようなEdgeオブジェクトが格納されます。

route[0]  A - Bのエッジ
route[1]  B - Cのエッジ

少し無理がありますが、使い方は以下のようになります。

var edge0 = A.edgeList[0]; // A - Bのエッジ
var edge1 = edge0.to.edgeList[0]; //B - Cのエッジ
var route = new Route(A, C, [ edge0, edge1 ] );

重み

エッジには重みがありました。これと同様に経路もエッジの集合なので重みがあります。経路(Route)に含まれるエッジ(route)の和を、その経路の重み(コスト)にします。今回、各エッジの重みは以下のものを想定します。

元のノード	先のノード	重み
A	B	2
B	C	4

そして、各エッジの重みから、経路の重みを求めるような関数は以下のようになります。

Route.prototype.getCost = function(){
	var total = 0;
	var f = this.from; //元のノード
	for(var i = 0; i < this.route.length; i++) {
		var edge = this.route[i];
		if(edge.from != f) return null;
		total += edge.cost;
		f = edge.to;
	}
	if(this.route[this.route.length - 1].to != f) return null;
	return total;
};

単純に足し算をしているだけですが、経路情報(route)がfromノードからtoノードへのものでない場合、エラーとなり、nullを返します。

Routeを文字列に

経路(Route)の文字列表現

Route.prototype.toString = function(){
	var len = this.route.length;
	if(len <= 0) return "";
	var str = this.route[0].from;
	for(var i = 1; i < this.route.length; i++) {
		str += " - " + this.route[i].from
	}
	str += " - " + this.route[this.route.length-1].to;
	return "(" + this.from + ", " + this.to + ", " + this.getCost() + ") " + str;
};

出力例は以下の通り。

(A, C, 6) A - B - C

Routeを複製する

ダイクストラで求める経路(Route)は一本だけではありません。そのため何本も経路が必要になります。例えば、以下のような一直線の経路があったとします。

A - B - C - D

例えば、AからCまでの経路が分っていれば、これをコピーすることで、AからDまでの経路をすぐに作ることができます。そのためRouteを複製する機能が必要となるわけです。ちなみに経路を表すのに、ツリーを使う場合もあります(たぶんこちらが主流です)。ツリーを利用すると、複数の経路の一部分を共有することができ、経路を効率的に表すことができます。ただし今回は一本一本、独立した経路を作ることにします。

Route.prototype.clone = function(){
	var array = this.route.clone();	
	return new Route(this.from, this.to, array);
};

/**
 * cloneメソッドをArrayのプロトタイプオブジェクトに追加
 */
Array.prototype.clone = function(){
	return Array.apply(null,this)
}

Routeオブジェクトにcloneメソッドを追加しました。このとき、配列だけはそのままコピーすることができませんので、配列専用のcloneメソッドを実装する必要があります。具体的には、Arrayのプロトタイプオブジェクトをいじっています。このように標準の機能のプロトタイプオブジェクトをいじるのは結構危険なので注意してください。

ノードの状態

ダイクストラアルゴリズムにおいて、各ノードの状態を分類すると、以下の3つに分けることができます。

• 未探索ノード
• 探索済みノード
• 探索予定ノード

「未探索ノード」は、どこにあるのか全く分からないノードのことを指します。「探索予定ノード」は、次に探索される候補になるノードのことです。この「探索予定ノード」から伸びるエッジは、まだチェックされていない状態になります。逆に「探索済みノード」は、そのノードから伸びるエッジを全てチェックした状態のノードになります。
経路を表すRouteオブジェクトに、この状態を示すためのプロパティcheckを設けます。

/**
 * あるノードからあるノードへの経路を示す
 * @param {Object} from
 * @param {Object} to
 * @param {Object} route　Edgeの配列
 */
function Route(from, to, route) {
	this.from = from;
	this.to = to;
	if(route) this.route = route;
	else this.route = new Array();
	this.check = false; //チェック用のフラグ
}

checkの取りうる値はtrueかfalseです。trueなら「探索済みノード」、falseなら「探索予定ノード」になります。「未探索ノード」については考慮する必要はありません。
ノードの状態を表すと言っているのに、Nodeオブジェクトではなく、Routeオブジェクトにcheckプロパティを設けました。少し不思議に思われるかもしれませんが、ちゃんと理由があります。ダイクストラで求める各Routeオブジェクトは、終点のノードと一対一で対応しているものです。そのため、Routeオブジェクトにcheckプロパティを設けても不思議ではありません。またNodeオブジェクトは元のグラフを表すためのものなので、それに手を加えるのは少しへんだと考え、Routeオブジェクトにcheckプロパティを設けることにしました。以後「探索済みノード」を「探索済み経路」、「探索予定ノード」を「探索予定経路」と呼ぶことにします。
今後、探索した経路は、リストに入れていくわけですが、「探索済み経路」と「探索予定経路」の区別は、checkプロパティを見ればわかるので、この二種類の経路(Route)を同じリストに混ぜて入れることができます。

ダイクストラの関数

いよいよメインの部分を作ります。dijkstra関数に始点ノードを渡すことで処理が開始し、最終的にRouteの配列として返ってきます。dijkstra関数は内部でdijkRecを呼び出します。dijkRecは再帰処理をすることによって、探索をすすめます。このとき、「探索済み経路」と「探索予定経路」は変数listの中に格納されていきます。
なお、dijkRecの内部は結構ややこしい処理をしています(これは私の実力のせいです)。再帰処理の初回は、現在の地点までの経路情報をもたないので、少しめんどくさい処理をしています。二回目以降の処理から見ていったほうが、分り易いかと思います。dijkRecの二回目以降の部分を見てみると、最初に「探索予定経路」のなかから、重みが一番小さいものを選んでいます。そして、この経路の先をさらに探索していくという形になります。最終的に、「探索予定経路」がなくなれば、探索が終了します。
「探索予定経路」は途中でどんどん追加されていきます。また、エッジをたどっていくと、「未探索ノード」だけでなく、「探索済み経路」や「探索予定経路」にもたどり着く場合があります。「探索済み経路」と「探索予定経路」までの経路や重みはすでに決定していますが、新しく発見した経路のほうが重みが小さい場合、こちらを最短経路にします。

/**
 * ダイクストラ
 */
function dijkstra(start) {
	var list = new Array();
	dijkRec(list, start);
	return list;
};

/**
 * 最短経路を再帰的に求める
 * @param {Object} list Routeの配列
 * @param {Object} start 初回のみ指定
 */
function dijkRec(list, start) {
	var isFirst = false; //初回かどうか
	var route; //今回選択するルート
	if(start != null){
		isFirst = true;
		route = new Route(null, start, new Array()); //ダミー用
	}else{ //二回目以降
		if(list.length <= 0) return;
		//コストが一番小さい経路を探す
		var min;
		var minIndex;
		for(var i = 0; i < list.length; i++) {
			var li = list[i];
			if(li.check) continue; //チェック済みならスキップ
			var cost = li.getCost();
			if( min > cost ){
				min = cost;
				minIndex = i;
			}else if(min == null){
				min = cost;
				minIndex = i;
			}
		}
		if(minIndex == null) return;
		route = list[minIndex];
	}
	route.check = true; //探索済みマーク
	//その経路から先を探索する
	var from = route.to;
	for(var i = 0; i < from.edgeList.length; i++) {
		var edge = from.edgeList[i];
		//edge.toがすでにリストにあるか調べる
		var check = false;
		for(var j = 0; j < list.length; j++) {
			if(edge.to == list[j].to){
				check = true;
				break;
			}
		}
		//探索予定経路を追加
		var r;
		if(!check){ //まだない場合
			if(!isFirst){
				//クローンから新しい経路を作る
				r = route.clone();
				r.to = edge.to; //宛先を書きかえ
				r.route.push(edge); //経路かきかえ
			}else{
				r = new Route(from, edge.to, [ edge ]);
			}
			list.push(r);
		} else { //すでにある場合
			if(list[j].getCost() > route.getCost() + edge.cost ) { //新しいルートのほうがコストが低い場合
				//クローンから新しいルートを作る
				r = route.clone();
				r.to = edge.to;
				r.route.push(edge); //ルートかきかえ
				r.check = list[j].check;
				list[j] = r; //入れ替え
			} else { //逆にコストが高い場合
				continue; // !!ここで終わり!!
			}
		}
	}
	dijkRec(list);
};

これを動作させるためのサンプルプログラムは以下のようになります。

//グラフ1
//
//(A, B, 1) A - B
//(A, C, 2) A - C
//(A, D, 1) A - D
//(A, E, 5) A - B - E
//(A, F, 3) A - D - F

var A = new Node("A");
var B = new Node("B");
var C = new Node("C");
var D = new Node("D");
var E = new Node("E");
var F = new Node("F");
A.addLink(B, 1);
A.addLink(C, 2);
A.addLink(D, 1);
B.addLink(E, 4);
C.addLink(B, 1);
C.addLink(F, 2);
D.addLink(F, 2);
F.addLink(D, 3);
F.addLink(E, 3);

//ダイクストラのテスト
var dijkList = dijkstra(A);

//見やすいようソート
dijkList.sort(function(a,b){
	if(a.from > b.from) return 1;
	else if(a.from < b.from) return -1;
	else {
		return a.to > b.to ? 1 : -1;		
	}
});	

for(var i = 0; i < dijkList.length; i++){
	document.write(dijkList[i]+"<br>");
}

以上でおわり

ダイクストラの部分はやはり苦戦しましたが、プログラムを実装したことで具体像を頭に思い描くことができました。ダイクストラって、テストの問題としてよくでてくるんですが、いつも忘れちゃうんですよね。これでしばらく忘れそうにありません。経路(Route)をツリー状にしたバージョンにもチャレンジしてみようと思います。最後にここまで全てのソースコードと添付ファイルをつけておきます。とりあえず動きますが、おそらくバグがいっぱい混じってます。

ソース

• index.html
• graph.js
• search.js

index.html

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Graph</title>
<script src="graph.js"></script>
<script src="search.js"></script>
</head>
<body onload="init()">

</body>
</html>

graph.js

/**
 * ノード
 * @param {Object} name ユニークな名前にすること
 * @param {Object} edgeList エッジを配列として保持
 */
function Node(name, edgeList) {
	this.name = name;
	if(typeof edgeList == "array") this.edgeList = edgeList;
	else this.edgeList = new Array();
	
	Node.prototype.addLink = function(node, cost) {
		var link = new Edge(this, node, cost);
		this.edgeList.push(link);
	};
	Node.prototype.toString = function() {
		return this.name;
	}
};

/**
 * エッジ
 * @param {Object} from 基のノード
 * @param {Object} to 次のノード
 * @param {Object} cost コスト
 */
function Edge(from, to, cost) {
	if(from) this.from = from;
	if(to) this.to = to;
	if(cost) this.cost = cost;
	else this.cost = 0;

	Edge.prototype.toString = function() {
		return this.from + " - " + this.to + "   " + this.cost;
	};
};

search.js

function init() {
/**
	//簡易版グラフ
	var A = new Node("A");
	var B = new Node("B");
	var C = new Node("C");
	A.addLink(B, 2);
	B.addLink(C, 4);
	C.addLink(A, 4);
**/

	//グラフ1
	//
	//(A, B, 1) A - B
	//(A, C, 2) A - C
	//(A, D, 1) A - D
	//(A, E, 5) A - B - E
	//(A, F, 3) A - D - F

	var A = new Node("A");
	var B = new Node("B");
	var C = new Node("C");
	var D = new Node("D");
	var E = new Node("E");
	var F = new Node("F");
	A.addLink(B, 1);
	A.addLink(C, 2);
	A.addLink(D, 1);
	B.addLink(E, 4);
	C.addLink(B, 1);
	C.addLink(F, 2);
	D.addLink(F, 2);
	F.addLink(D, 3);
	F.addLink(E, 3);

	/*************************************
	 * 上のグラフのAノードだけが与えられているとする
	 *************************************/
	

/**	
	//リスト化
	var list = toList(A);

    list.sort(function(a, b){
        return a.from > b.from ? 1 : -1;
    });
	for (var i = 0; i < list.length; i++) {
		document.write(list[i] + "<br>");
	}
**/

/**	
	var edge0 = A.edgeList[0]; // A - Bのエッジ
	var edge1 = edge0.to.edgeList[0]; //B - Eのエッジ
	var route = new Route(A, C, [ edge0, edge1 ] );
	var cost = route.getCost();
	alert(cost); //5
**/


	//ダイクストラのテスト
	var dijkList = dijkstra(A);
	
	dijkList.sort(function(a,b){
		if(a.from > b.from) return 1;
		else if(a.from < b.from) return -1;
		else {
			return a.to > b.to ? 1 : -1;		
		}
	});		
	for(var i = 0; i < dijkList.length; i++){
		document.write(dijkList[i]+"<br>");
	}
}

/**
 * cloneメソッドをArrayのプロトタイプオブジェクトに追加
 */
Array.prototype.clone = function(){
    return Array.apply(null,this)
}

/**
 * startとgoalはnodeオブジェクト
 * @param {Object} start
 * @param {Object} goal
 */
function toList(start) {
	var list = new Array();
	var finish  = new Array(); //探索終了
	listRec(start, list, finish);
	return list;
};

/**
 * toListから再帰的に呼び出される
 * @param {Object} node
 * @param {Object} list
 * @param {Object} finish
 */
function listRec(node, list, finish) {
	for (var j = 0; j < finish.length; j++) { //すでに登録済みかどうか調べる
		if (node == finish[j]) {
			return; //抜ける
		}
	}
	finish.push(node); //探索済みノードに追加
	for (var i = 0; i < node.edgeList.length; i++) { //エッジをリストに登録
		var edge = node.edgeList[i];
		list.push(edge); //リストに追加
		listRec(edge.to, list, finish)
	}
};

/**
 * ダイクストラ
 */
function dijkstra(start) {
	var list = new Array();
	dijkRec(list, start);
	return list;
};

/**
 * 最短経路を再帰的に求める
 * @param {Object} list Routeの配列
 * @param {Object} start 初回のみ指定
 */
function dijkRec(list, start) {
	var isFirst = false; //初回かどうか
	var route; //今回選択するルート
	if(start != null){
		isFirst = true;
		route = new Route(null, start, new Array()); //ダミー用
	}else{ //二回目以降
		if(list.length <= 0) return;
		//コストが一番小さい経路を探す
		var min;
		var minIndex;
		for(var i = 0; i < list.length; i++) {
			var li = list[i];
			if(li.check) continue; //チェック済みならスキップ
			var cost = li.getCost();
			if( min > cost ){
				min = cost;
				minIndex = i;
			}else if(min == null){
				min = cost;
				minIndex = i;
			}
		}
		if(minIndex == null) return;
		route = list[minIndex];
	}
	route.check = true; //探索済みマーク
	//その経路から先を探索する
	var from = route.to;
	for(var i = 0; i < from.edgeList.length; i++) {
		var edge = from.edgeList[i];
		//edge.toがすでにリストにあるか調べる
		var check = false;
		for(var j = 0; j < list.length; j++) {
			if(edge.to == list[j].to){
				check = true;
				break;
			}
		}
		//探索候補のルートを追加
		var r;
		if(!check){ //まだない場合
			if(!isFirst){
				//クローンから新しいルートを作る
				r = route.clone();
				r.to = edge.to; //宛先を書きかえ
				r.route.push(edge); //ルートかきかえ
			}else{
				r = new Route(from, edge.to, [ edge ]);
			}
			list.push(r);
		} else { //すでにある場合
			if(list[j].getCost() > route.getCost() + edge.cost ) { //新しいルートのほうがコストが低い場合
				//クローンから新しいルートを作る
				r = route.clone();
				r.to = edge.to;
				r.route.push(edge); //ルートかきかえ
				r.check = list[j].check;
				list[j] = r; //入れ替え
			} else { //逆にコストが高い場合
				continue; // !!ここで終わり!!
			}
		}
	}
	dijkRec(list);
};

/**
 * あるノードからあるノードへの経路を示す
 * @param {Object} from
 * @param {Object} to
 * @param {Object} route　Edgeの配列
 */
function Route(from, to, route) {
	this.from = from;
	this.to = to;
	if(route) this.route = route; //Edgeの集合
	else this.route = new Array();
	this.check = false; //チェック用のフラグ
}
Route.prototype.toString = function(){
	var len = this.route.length;
	if(len <= 0) return "";
	var str = this.route[0].from;
	for(var i = 1; i < this.route.length; i++) {
		str += " - " + this.route[i].from
	}
	str += " - " + this.route[this.route.length-1].to;
	return "(" + this.from + ", " + this.to + ", " + this.getCost() + ") " + str;
};
Route.prototype.getCost = function(){
	var total = 0;
	var f = this.from; //元のノード
	for(var i = 0; i < this.route.length; i++) {
		var edge = this.route[i];
		if(edge.from != f) return null;
		total += edge.cost;
		f = edge.to;
	}
	if(this.route[this.route.length - 1].to != f) return null;
	return total;
};
Route.prototype.clone = function(){
	var array = this.route.clone();	
	return new Route(this.from, this.to, array);
};

ダウンロード

HelloGraph.zip