greed.cs

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

////////////////////////////////////
////   贪心法          ////////////
//////////////////////////////////
using System;
using System.Collections;
using System.Windows.Forms;
using System.Drawing;

namespace short_path
{
	/// <summary>
	/// greed 的摘要说明。
	/// </summary>
	public class Greed
	{
		Form1 fr = null;
		Storage stg = null;
		PictureBox pic = null;
		public Hashtable edges;
		int nodeCount = 0;
		public Greed(Storage s, Form1 f)
		{
			fr = f;
			stg = s;
			pic = f.pic;
			foreach(nodeInfo ni in stg.points.Values)
			{
				ni.w = double.MaxValue;
			}
			((nodeInfo)stg.points[stg.startpoint]).w = 0;
			fr.label2.Text = Convert.ToString(nodeCount);
		}

		public void comput()
		{
			string curPoint = stg.startpoint;
			edges = new Hashtable();
			edges[stg.startpoint] = curPoint;
			while(curPoint != stg.endpoint)
			{
				double minw = double.MaxValue;
				string strmin = null, strpa = null;
				foreach(string strni in edges.Keys)
				{
					nodeInfo cni = (nodeInfo)stg.points[strni];
					foreach(string strni2 in cni.Keys)
					{
						if(edges.ContainsKey(strni2) == false && minw > cni.w+((nodeInfo)cni[strni2]).w)
						{
							minw = cni.w+((nodeInfo)cni[strni2]).w;
							((nodeInfo)stg.points[strni2]).w = minw;
							strmin = strni2;
							strpa = strni;
						}
					}
				}
				if(minw == double.MaxValue)	continue;
				
				fr.drawcur(strpa, edges,true);

				edges[strmin] = strpa;
				curPoint = strmin;
				nodeCount++;
				fr.label2.Text = Convert.ToString(nodeCount);
				fr.label4.Text = Convert.ToString(((nodeInfo)stg.points[strmin]).w);
			}
			if(curPoint != stg.endpoint)	MessageBox.Show("没找到");
			else 
			{
				fr.drawcur(stg.endpoint, edges, false);
				fr.label4.Text = Convert.ToString(((nodeInfo)stg.points[stg.endpoint]).w);
			}
		}
	}
}