trace.cs

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

////////////////////////////////////
////   回溯法          ////////////
//////////////////////////////////
using System;
using System.Collections;
using System.Drawing;
using System.Windows.Forms;

namespace short_path
{
	/// <summary>
	/// trace 的摘要说明。
	/// </summary>
	public class Trace
	{
		Form1 fr = null;
		Storage stg = null;
		double dmin = 0;
		Hashtable visited = null;
		PictureBox pic;
		int nodeCount = 0;

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

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

		private void visite(string cur)
		{
			fr.label4.Text = Convert.ToString(((nodeInfo)stg.points[cur]).w);
			nodeCount++;
			fr.label2.Text = Convert.ToString(nodeCount);
			if(cur == stg.endpoint)
			{
				if(dmin > ((nodeInfo)stg.points[cur]).w)
				{
					dmin = ((nodeInfo)stg.points[cur]).w;
				}
			}
			else
			{
				foreach(string strni in ((nodeInfo)stg.points[cur]).Keys)
				{
					if(visited[cur].ToString() != strni	&&	
						((nodeInfo)stg.points[strni]).w > ((nodeInfo)stg.points[cur]).w + ((nodeInfo)((nodeInfo)stg.points[cur])[strni]).w	&&	
						dmin >((nodeInfo)stg.points[cur]).w + ((nodeInfo)((nodeInfo)stg.points[cur])[strni]).w)
					{
						((nodeInfo)stg.points[strni]).w = ((nodeInfo)stg.points[cur]).w + ((nodeInfo)((nodeInfo)stg.points[cur])[strni]).w;
						visited[strni] = cur;
						fr.drawcur(strni,visited,true);
						visite(strni);
					}
				}
			}
		}

		public void comput()
		{
			visite(stg.startpoint);
			fr.label4.Text = Convert.ToString(((nodeInfo)stg.points[stg.endpoint]).w);
			fr.drawcur(stg.endpoint,visited, false);
		}
	}
}