dyla.cs

四种算法求最短路径的例子

////////////////////////////////////
////   动态规划法      ////////////
//////////////////////////////////
using System;
using System.Collections;
using System.Windows.Forms;

namespace short_path
{
	/// <summary>
	/// DyLa 的摘要说明。
	/// </summary>
	public class DyLa
	{
		Form1 fr = null;
		Storage stg = null;
		Hashtable visited = null;
		Queue act = null;
		int nodeCount = 0;

		public DyLa(Storage s, Form1 f)
		{
			fr = f;
			fr.label2.Text = Convert.ToString(nodeCount);

			stg = s;
			visited = new Hashtable();
			act = new Queue();
			foreach(nodeInfo ni in stg.points.Values)
			{
				ni.w = double.MaxValue;
			}
			((nodeInfo)stg.points[stg.startpoint]).w = 0;
			act.Enqueue(stg.startpoint);
			visited[stg.startpoint] = stg.startpoint;
		}

		public void comput()
		{
			while(act.Count != 0)
			{
				string cur = act.Dequeue().ToString();
				fr.label4.Text = Convert.ToString(((nodeInfo)stg.points[cur]).w);
				foreach(string ni in  ((nodeInfo)stg.points[cur]).Keys)
				{
					if(((nodeInfo)stg.points[ni]).w > ((nodeInfo)stg.points[cur]).w + ((nodeInfo)((nodeInfo)stg.points[cur])[ni]).w)
					{
						((nodeInfo)stg.points[ni]).w = ((nodeInfo)stg.points[cur]).w + ((nodeInfo)((nodeInfo)stg.points[cur])[ni]).w;
						visited[ni] = cur;
						act.Enqueue(ni);
						fr.drawcur(ni,visited,true);
						nodeCount++;
						fr.label2.Text = Convert.ToString(nodeCount);
					}
				}
			}
			fr.drawcur(stg.endpoint,visited, false);
			fr.label4.Text = Convert.ToString(((nodeInfo)stg.points[stg.endpoint]).w);
		}
	}
}