解析

• ダイクストラ法による最短経路問題

　スタート地点からゴール地点までの経路が複数ある場合の最短経路を求めるアルゴリズムです。
ひとつ考えられるのは、全ての組み合わせを抽出して最短のものを選ぶという方法がありますが、これは大量の経路が存在する場合、計算に非常に時間がかかります。ダイクストラ法では隣接する点の最小値を集計していくことによって、スタート地点から全地点までの最短経路を順番に確定していきます。
応用としては電車の路線検索等が考えられます。実際の路線検索では距離だけでなく、時間や運賃など複数のファクターを考慮に入れる必要があるでしょう。 本サイトではアルゴリズムについての詳細は省略し、C#による実装方法とソフトウェアのソースコードを公開します。

ソフトウェアの紹介

公開しているソフトウェアを紹介致します。

左ボタンクリックにより、ノードの位置を複数定義しておきます。

次に、左ボタンドラッグにより、ノードとノードの間をつなぐブランチを定義します。

ノードをもう一度左クリックすると、赤丸になり、赤丸をもう一度クリックすると緑丸になります。赤丸がスタート地点、緑丸がゴール地点となります。スタートからゴールまでの最短経路が赤線で表示されます。経路が2通りだけなら合計して比べればよいのですが、経路パターンが多数ある場合はダイクストラ法を使います。

ソースコードのダウンロード

バイナリのダウンロード

以下はアルゴリズム部分のソースコードです。画面描画部分はプロジェクトをダウンロードして参照してください。

		
/// <summary>ブランチクラス</summary>
public class DijkstraBranch
{
	public readonly DijkstraNode Node1;	// ノード1
	public readonly DijkstraNode Node2;	// ノード2
	public readonly double Distance;	// 距離

	public DijkstraBranch( DijkstraNode node1, DijkstraNode node2, double dDistance )
	{
		Node1 = node1;
		Node2 = node2;
		Distance = dDistance;
	}
}
/// <summary>ノードクラス</summary>
public class DijkstraNode
{
	/// <summary>最短経路確定状態の列挙体</summary>
	public enum NodeStatus
	{
		NotYet,		// 未確定状態
		Temporary,	// 仮確定状態
		Completed	// 確定状態
	}

	public double Distance;				// 距離
	public DijkstraNode SourceNode;		// ソースノード
	public NodeStatus Status;			// 最短経路確定状態
	public Point Position;				// ノード位置

}

/// <summary>ダイクストラ法アルゴリズム実装</summary>
public class Dijkstra
{
	// ブランチ
	public List<DijkstraBranch> Branches
	{
		get
		{
			return _branches;
		}
		set
		{
			_branches = value;
		}
	}
	// ノード
	public List<DijkstraNode> Nodes
	{
		get
		{
			return _nodes;
		}
	}

	private List<DijkstraBranch> _branches;
	private List<DijkstraNode> _nodes;

	/// <summary>コンストラクタ</summary>
	/// <param name="nNodeCount">全ノード数</param>
	public Dijkstra( int nNodeCount )
	{
		_nodes = new List<DijkstraNode>();
		for( int i = 0; i < nNodeCount; i++ )
		{
			_nodes.Add( new DijkstraNode() );
		}
	}

	/// <summary>最短経路計算実行</summary>
	/// <param name="nStart">スタートノードのインデックス</param>
	/// <returns>検索回数</returns>
	public int Execute( DijkstraNode startNode )
	{
		if( startNode == null ) return 0;

		// 全節点で距離を無限大，未確定とする
		foreach( DijkstraNode node in _nodes )
		{
			node.Distance = int.MaxValue;
			node.Status = DijkstraNode.NodeStatus.NotYet;
			node.SourceNode = null;
		}

		// 始点では距離はゼロ，確定とする
		startNode.Distance = 0;
		startNode.Status = DijkstraNode.NodeStatus.Completed;
		startNode.SourceNode = null;

		DijkstraNode scanNode = startNode;
		int nCount = 0;
		while( scanNode != null )
		{
			UpdateNodeProp( scanNode );		// 隣接点のノードを更新
			scanNode = FindMinNode();		// 最短経路をもつノードを検索
			nCount++;
		}
		return nCount;
	}

	/// <summary>指定ノードに隣接するノードの最短距離を計算する。</summary>
	/// <param name="sourceNode">指定ノード</param>
	private void UpdateNodeProp( DijkstraNode sourceNode )
	{
		if( _branches == null ) return;

		DijkstraNode destinationNode;
		double dTotalDistance;

		// ブランチリストの中から指定ノードに関連しているものを検索
		foreach( DijkstraBranch branch in _branches )
		{
			destinationNode = null;
			if( branch.Node1.Equals( sourceNode ) == true )
			{
				destinationNode = branch.Node2;
			}
			else if( branch.Node2.Equals( sourceNode ) == true )
			{
				destinationNode = branch.Node1;
			}
			else
			{
				continue;
			}
			// 隣接ノードを見つけた。

			// 確定しているノードは無視。
			if( destinationNode.Status == DijkstraNode.NodeStatus.Completed ) continue;

			// ノードの現在の距離に枝の距離を加える。
			dTotalDistance = sourceNode.Distance + branch.Distance;

			if( destinationNode.Distance <= dTotalDistance ) continue;

			// 現在の仮の最短距離よりもっと短い行き方を見つけた。
			destinationNode.Distance = dTotalDistance;	// 仮の最短距離
			destinationNode.SourceNode = sourceNode;
			destinationNode.Status = DijkstraNode.NodeStatus.Temporary;
		}
	}

	/// <summary>未確定ノードの中で最短経路をもつノードを検索</summary>
	/// <returns>最短経路をもつノード</returns>
	private DijkstraNode FindMinNode()
	{
		double dMinDistance = int.MaxValue; // 最小値を最初無限大とする

		DijkstraNode Finder = null;

		// 全てのノードをチェック
		foreach( DijkstraNode node in _nodes )
		{
			// 確定したノードは無視
			if( node.Status == DijkstraNode.NodeStatus.Completed ) continue;

			// 未確定のノードの中で最短距離のノードを探す
			if( node.Distance >= dMinDistance ) continue;

			dMinDistance = node.Distance;
			Finder = node;
		}
		if( Finder == null ) return null;

		// 最短距離を見つけた。このノードは確定！
		Finder.Status = DijkstraNode.NodeStatus.Completed;
		return Finder;

	}

}