lc.cs

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

////////////////////////////////////
////   分枝限界法法     ////////////
//////////////////////////////////
using System;
using System.Collections;
using System.Windows.Forms;

namespace short_path
{
	public class LCnode : Hashtable
	{
		public string point;
		public double r;
		public double w;
	}

	internal class MyComp : IComparer
	{
		#region IComparer 成员

		public int Compare(object x, object y)
		{
			if(	((LCnode)x).w > ((LCnode)y).w )
				return	1;
			else return -1;
		}

		#endregion

	}

	/// <summary>
	/// LC 的摘要说明。
	/// </summary>
	public class LC
	{
		Form1 fr = null;
		Storage stg = null;
		Hashtable visited = null;
		int nodeCount = 0;
		LCnode startn = null;
		double U = double.MaxValue;
		
		public LC(Storage s, Form1 f)
		{
			fr = f;
			fr.label2.Text = Convert.ToString(nodeCount);

			stg = s;
			visited = new Hashtable();
			foreach(nodeInfo ni in stg.points.Values)
			{
				ni.w = 0;
			}
			U = double.MaxValue;
			visited[stg.startpoint] = stg.startpoint;
			startn = new LCnode();
			startn.point = stg.startpoint;
			startn.w = 0;
			createGuiYue(startn, stg.points);
		}

		private void createGuiYue(LCnode n, Hashtable t)
		{
			n.r = 0;
			//行归约
			foreach(string ni in t.Keys)
			{
				n[ni] = new nodeInfo();
				if(ni == n.point)
				{
					foreach(string ni2 in ((nodeInfo)stg.points[ni]).Keys)
					{
						((nodeInfo)n[ni])[ni2]  = new nodeInfo();
						((nodeInfo)((nodeInfo)n[ni])[ni2]).w = double.MaxValue;
					}
				}
				else
				{
					double locmin = double.MaxValue;
					foreach(nodeInfo ni2 in ((nodeInfo)stg.points[ni]).Values)
					{
						if(locmin > ni2.w)	locmin = ni2.w;
					}
					if(locmin == double.MaxValue)	locmin = 0;
					foreach(string ni2 in ((nodeInfo)stg.points[ni]).Keys)
					{
						if(((nodeInfo)n[ni]).ContainsKey(ni2) && ((nodeInfo)((nodeInfo)n[ni])[ni2]).w != double.MaxValue)
						{
							((nodeInfo)((nodeInfo)n[ni])[ni2]).w  = ((nodeInfo)((nodeInfo)t[ni])[ni2]).w - locmin;
							if( ((nodeInfo)((nodeInfo)n[ni])[ni2]).w < 0)	((nodeInfo)((nodeInfo)n[ni])[ni2]).w = 0;
						}
					}
					n.r += locmin;
				}
			}
			//列归约
			foreach(string ni in t.Keys)
			{
				if(ni == n.point)
				{
					foreach(string ni2 in t.Keys)
					{
						if(((nodeInfo)t[ni2]).ContainsKey(ni) == true)
						{
							if(((nodeInfo)n[ni2]).ContainsKey(ni) == false)
							{
								((nodeInfo)n[ni2])[ni] = new nodeInfo();
							}
							((nodeInfo)((nodeInfo)n[ni2])[ni]).w  = double.MaxValue;
						}
					}
				}
				else
				{
					double locmin = double.MaxValue;
					foreach(nodeInfo ni2 in t.Values)
					{
						if(ni2.ContainsKey(ni) == true)
						{
							if( locmin > ((nodeInfo)(ni2[ni])).w )	locmin = ((nodeInfo)(ni2[ni])).w;
						}
					}
					if(locmin == double.MaxValue)	locmin = 0;
					foreach(string ni2 in t.Keys)
					{
						if(((nodeInfo)t[ni2]).ContainsKey(ni) == true)
						{
							if(((nodeInfo)n[ni2]).ContainsKey(ni) &&  ((nodeInfo)((nodeInfo)n[ni2])[ni]).w != double.MaxValue)
							{
								((nodeInfo)((nodeInfo)n[ni2])[ni]).w  = ((nodeInfo)((nodeInfo)t[ni2])[ni]).w - locmin;
								if(((nodeInfo)((nodeInfo)n[ni2])[ni]).w < 0)	((nodeInfo)((nodeInfo)n[ni2])[ni]).w = 0;
							}
						}
					}
					n.r += locmin;
				}
			}
		}

		public void comput()
		{
			MyComp mycomp = new MyComp();
			SortedList sl = new SortedList(mycomp);

			sl[startn] = stg.startpoint;
			while(sl.Count != 0)
			{
				LCnode n = (LCnode)sl.GetKey(0);
				sl.RemoveAt(0);
				foreach(string ni in ((nodeInfo)stg.points[n.point]).Keys)
				{
					LCnode curn = new LCnode();
					curn.point = ni;
					createGuiYue(curn, n);//((nodeInfo)((nodeInfo)stg.points[n.point])[ni]).w
					curn.w = ((nodeInfo)stg.points[n.point]).w + ((nodeInfo)((nodeInfo)stg.points[n.point])[ni]).w + curn.r;
					if(curn.point == stg.endpoint)
					{
						if(U > ((nodeInfo)stg.points[n.point]).w + ((nodeInfo)((nodeInfo)stg.points[n.point])[ni]).w)
						{
							U = ((nodeInfo)stg.points[n.point]).w + ((nodeInfo)((nodeInfo)stg.points[n.point])[ni]).w;
							((nodeInfo)stg.points[stg.endpoint]).w = U;
							visited[stg.endpoint] = n.point;
							nodeCount++;
							fr.label2.Text = Convert.ToString(nodeCount);
						}
					}
					else
					{
						if(curn.w < U)
						{
							if(visited.ContainsKey(ni) == false)
							{
								((nodeInfo)stg.points[ni]).w = ((nodeInfo)stg.points[n.point]).w + ((nodeInfo)((nodeInfo)stg.points[n.point])[ni]).w ;
								sl[curn] = ni;
								visited[ni] = n.point;
								nodeCount++;
								fr.label2.Text = Convert.ToString(nodeCount);
								fr.label4.Text = Convert.ToString(((nodeInfo)stg.points[ni]).w);
								fr.drawcur(ni, visited, true);
							}
							else if(((nodeInfo)stg.points[ni]).w + curn.r > curn.w)
							{
								((nodeInfo)stg.points[ni]).w = ((nodeInfo)stg.points[n.point]).w + ((nodeInfo)((nodeInfo)stg.points[n.point])[ni]).w;
								int itmp = 0;
								foreach(string strtmp in sl.Values)
								{
									if(ni == strtmp)	break;
									else	itmp++;
								}
								if(itmp < sl.Count)	sl.RemoveAt(itmp);
								sl[curn] = ni;
								visited[ni] = n.point;
								nodeCount++;
								fr.label2.Text = Convert.ToString(nodeCount);
								fr.label4.Text = Convert.ToString(((nodeInfo)stg.points[ni]).w);
								fr.drawcur(ni, visited, true);
							}
						}
					}
				}
			}
			fr.drawcur(stg.endpoint, visited, false);
			fr.label4.Text = Convert.ToString(((nodeInfo)stg.points[stg.endpoint]).w);
		}		
	}
}