form1.cs

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

using System;
using System.Drawing;
using System.Collections;
using System.ComponentModel;
using System.Windows.Forms;
using System.Data;
using System.Threading;

namespace short_path
{
	/// <summary>
	/// Form1 的摘要说明。
	/// </summary>
	public class Form1 : System.Windows.Forms.Form
	{
		public System.Windows.Forms.PictureBox pic;
		/// <summary>
		/// 必需的设计器变量。
		/// </summary>
		private System.ComponentModel.Container components = null;
		private System.Windows.Forms.Button button2;
		private System.Windows.Forms.Button button3;
		public System.Windows.Forms.TrackBar trackBar1;
		private System.Windows.Forms.Button button4;
		private System.Windows.Forms.Label label1;
		public System.Windows.Forms.Label label2;

		Storage stg = null;
		private System.Windows.Forms.Button button1;
		private System.Windows.Forms.Label label3;
		public System.Windows.Forms.Label label4;
		Thread th = null;

		public Form1()
		{
			//
			// Windows 窗体设计器支持所必需的
			//
			InitializeComponent();
			this.SetStyle(ControlStyles.ResizeRedraw, true);

			stg = new Storage();
			stg.readFile();
			((nodeInfo)(stg.points[stg.startpoint])).color = Color.Yellow;
			((nodeInfo)(stg.points[stg.endpoint])).color = Color.Red;
			pic.Invalidate();
		}

		/// <summary>
		/// 清理所有正在使用的资源。
		/// </summary>
		protected override void Dispose( bool disposing )
		{
			if( disposing )
			{
				if (components != null) 
				{
					components.Dispose();
				}
			}
			base.Dispose( disposing );
		}

		#region Windows 窗体设计器生成的代码
		/// <summary>
		/// 设计器支持所需的方法 - 不要使用代码编辑器修改
		/// 此方法的内容。
		/// </summary>
		private void InitializeComponent()
		{
			this.pic = new System.Windows.Forms.PictureBox();
			this.button2 = new System.Windows.Forms.Button();
			this.button3 = new System.Windows.Forms.Button();
			this.trackBar1 = new System.Windows.Forms.TrackBar();
			this.button4 = new System.Windows.Forms.Button();
			this.label1 = new System.Windows.Forms.Label();
			this.label2 = new System.Windows.Forms.Label();
			this.button1 = new System.Windows.Forms.Button();
			this.label3 = new System.Windows.Forms.Label();
			this.label4 = new System.Windows.Forms.Label();
			((System.ComponentModel.ISupportInitialize)(this.trackBar1)).BeginInit();
			this.SuspendLayout();
			// 
			// pic
			// 
			this.pic.Anchor = ((System.Windows.Forms.AnchorStyles)((((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Bottom) 
				| System.Windows.Forms.AnchorStyles.Left) 
				| System.Windows.Forms.AnchorStyles.Right)));
			this.pic.BackColor = System.Drawing.Color.White;
			this.pic.Location = new System.Drawing.Point(96, 8);
			this.pic.Name = "pic";
			this.pic.Size = new System.Drawing.Size(648, 360);
			this.pic.TabIndex = 1;
			this.pic.TabStop = false;
			this.pic.Paint += new System.Windows.Forms.PaintEventHandler(this.pic_Paint);
			this.pic.MouseDown += new System.Windows.Forms.MouseEventHandler(this.pic_MouseDown);
			// 
			// button2
			// 
			this.button2.Location = new System.Drawing.Point(8, 24);
			this.button2.Name = "button2";
			this.button2.TabIndex = 2;
			this.button2.Text = "贪心法";
			this.button2.Click += new System.EventHandler(this.button2_Click);
			// 
			// button3
			// 
			this.button3.Location = new System.Drawing.Point(8, 64);
			this.button3.Name = "button3";
			this.button3.TabIndex = 3;
			this.button3.Text = "回溯法";
			this.button3.Click += new System.EventHandler(this.button3_Click);
			// 
			// trackBar1
			// 
			this.trackBar1.Anchor = ((System.Windows.Forms.AnchorStyles)(((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Bottom) 
				| System.Windows.Forms.AnchorStyles.Right)));
			this.trackBar1.AutoSize = false;
			this.trackBar1.LargeChange = 20;
			this.trackBar1.Location = new System.Drawing.Point(760, 8);
			this.trackBar1.Maximum = 1000;
			this.trackBar1.Minimum = 500;
			this.trackBar1.Name = "trackBar1";
			this.trackBar1.Orientation = System.Windows.Forms.Orientation.Vertical;
			this.trackBar1.Size = new System.Drawing.Size(24, 379);
			this.trackBar1.TabIndex = 4;
			this.trackBar1.TickStyle = System.Windows.Forms.TickStyle.None;
			this.trackBar1.Value = 900;
			// 
			// button4
			// 
			this.button4.Location = new System.Drawing.Point(8, 104);
			this.button4.Name = "button4";
			this.button4.TabIndex = 5;
			this.button4.Text = "动态规划法";
			this.button4.Click += new System.EventHandler(this.button4_Click);
			// 
			// label1
			// 
			this.label1.Anchor = ((System.Windows.Forms.AnchorStyles)((System.Windows.Forms.AnchorStyles.Bottom | System.Windows.Forms.AnchorStyles.Left)));
			this.label1.Location = new System.Drawing.Point(88, 376);
			this.label1.Name = "label1";
			this.label1.Size = new System.Drawing.Size(104, 32);
			this.label1.TabIndex = 6;
			this.label1.Text = "扩展节点数（包括重新扩展节点）：";
			// 
			// label2
			// 
			this.label2.Anchor = ((System.Windows.Forms.AnchorStyles)((System.Windows.Forms.AnchorStyles.Bottom | System.Windows.Forms.AnchorStyles.Left)));
			this.label2.Location = new System.Drawing.Point(208, 384);
			this.label2.Name = "label2";
			this.label2.Size = new System.Drawing.Size(88, 16);
			this.label2.TabIndex = 7;
			this.label2.Tag = "";
			this.label2.Text = "0";
			// 
			// button1
			// 
			this.button1.Location = new System.Drawing.Point(8, 152);
			this.button1.Name = "button1";
			this.button1.TabIndex = 8;
			this.button1.Text = "分枝限界法";
			this.button1.Click += new System.EventHandler(this.button1_Click);
			// 
			// label3
			// 
			this.label3.Location = new System.Drawing.Point(328, 384);
			this.label3.Name = "label3";
			this.label3.Size = new System.Drawing.Size(72, 23);
			this.label3.TabIndex = 9;
			this.label3.Text = "路径长度：";
			// 
			// label4
			// 
			this.label4.Location = new System.Drawing.Point(408, 384);
			this.label4.Name = "label4";
			this.label4.Size = new System.Drawing.Size(256, 23);
			this.label4.TabIndex = 10;
			this.label4.Text = "0";
			// 
			// Form1
			// 
			this.AutoScaleBaseSize = new System.Drawing.Size(6, 14);
			this.ClientSize = new System.Drawing.Size(798, 415);
			this.Controls.Add(this.label4);
			this.Controls.Add(this.label3);
			this.Controls.Add(this.button1);
			this.Controls.Add(this.label2);
			this.Controls.Add(this.label1);
			this.Controls.Add(this.button4);
			this.Controls.Add(this.trackBar1);
			this.Controls.Add(this.button3);
			this.Controls.Add(this.button2);
			this.Controls.Add(this.pic);
			this.FormBorderStyle = System.Windows.Forms.FormBorderStyle.Fixed3D;
			this.Name = "Form1";
			this.Text = "求最短路径";
			((System.ComponentModel.ISupportInitialize)(this.trackBar1)).EndInit();
			this.ResumeLayout(false);

		}
		#endregion

		/// <summary>
		/// 应用程序的主入口点。
		/// </summary>
		[STAThread]
		static void Main() 
		{
			Application.Run(new Form1());
		}

		private void pic_Paint(object sender, System.Windows.Forms.PaintEventArgs e)
		{
			Graphics g = e.Graphics;
			
			if(stg != null)
			{
				float kx = (float)(((PictureBox)sender).Width*0.9)/(stg.maxx-stg.minx);
				float ky = (float)(((PictureBox)sender).Height*0.9)/(stg.maxy-stg.miny);
				foreach(nodeInfo ni in stg.points.Values)
				{
					int cx = (int)((ni.point.X-stg.minx)*kx);
					int cy = (int)((ni.point.Y-stg.miny)*ky);
					foreach(nodeInfo ni2 in ni.Values)
					{
						g.DrawLine(new Pen(ni2.color, 2), cx+10, cy+10, (ni2.point.X-stg.minx)*kx+10, (ni2.point.Y-stg.miny)*ky+10);
					}
					g.FillEllipse(new SolidBrush(ni.color), cx+5, cy+5,10,10);
					ni.srcPoint.X = cx+5;
					ni.srcPoint.Y = cy+5;
				}
			}
		}

		private void pic_MouseDown(object sender, System.Windows.Forms.MouseEventArgs e)
		{
			if(e.Button == MouseButtons.Left)
			{
				foreach(nodeInfo ni in stg.points.Values)
				{
					if(e.X>ni.srcPoint.X && e.X<ni.srcPoint.X+10 && e.Y>ni.srcPoint.Y && e.Y<ni.srcPoint.Y+10 )
					{
						((nodeInfo)(stg.points[stg.startpoint])).color = Color.Blue;
						ni.color = Color.Yellow;
						stg.startpoint = ni.point.X.ToString()+','+ni.point.Y.ToString();
						pic.Invalidate();
					}
				}
			}
			else
			{
				foreach(nodeInfo ni in stg.points.Values)
				{
					if(e.X>ni.srcPoint.X && e.X<ni.srcPoint.X+10 && e.Y>ni.srcPoint.Y && e.Y<ni.srcPoint.Y+10 )
					{
						((nodeInfo)(stg.points[stg.endpoint])).color = Color.Blue;
						ni.color = Color.Red;
						stg.endpoint = ni.point.X.ToString()+','+ni.point.Y.ToString();
						pic.Invalidate();
					}
				}
			}
		}


		private void button2_Click(object sender, System.EventArgs e)
		{
			foreach(nodeInfo ni in stg.points.Values)
			{
				foreach(nodeInfo ni2 in ni.Values)
				{
					ni2.color = Color.Pink;
				}
			}
			pic.Invalidate();
			Greed g = new Greed(stg, this);
			ThreadStart ts = new ThreadStart(g.comput);
			if(th != null && th.IsAlive)	th.Abort();
			th = new Thread(ts);
			th.Start();
		}

		private void button3_Click(object sender, System.EventArgs e)
		{
			foreach(nodeInfo ni in stg.points.Values)
			{
				foreach(nodeInfo ni2 in ni.Values)
				{
					ni2.color = Color.Pink;
				}
			}
			pic.Invalidate();
			Trace trace = new Trace(stg, this);
			ThreadStart ts = new ThreadStart(trace.comput);
			if(th != null && th.IsAlive)	th.Abort();
			th = new Thread(ts);
			th.Start();
		}

		private void button4_Click(object sender, System.EventArgs e)
		{
			foreach(nodeInfo ni in stg.points.Values)
			{
				foreach(nodeInfo ni2 in ni.Values)
				{
					ni2.color = Color.Pink;
				}
			}
			pic.Invalidate();
			DyLa dl = new DyLa(stg, this);
			ThreadStart ts = new ThreadStart(dl.comput);
			if(th != null && th.IsAlive)	th.Abort();
			th = new Thread(ts);
			th.Start();
		}

		public void drawcur(string cur, Hashtable visited, bool d)
		{
			foreach(nodeInfo ni in stg.points.Values)
			{
				foreach(nodeInfo ni2 in ni.Values)
				{
					ni2.color = Color.Pink;
				}
			}
			while(cur != stg.startpoint)
			{
				((nodeInfo)((nodeInfo)stg.points[cur])[visited[cur].ToString()]).color = Color.Black;
				((nodeInfo)((nodeInfo)stg.points[visited[cur].ToString()])[cur]).color = Color.Black;
				cur = visited[cur].ToString();
			}
			pic.Invalidate();
			if(d == true)
			{
				System.Threading.Thread.Sleep(this.trackBar1.Maximum - this.trackBar1.Value);
			}
		}

		private void button1_Click(object sender, System.EventArgs e)
		{
			foreach(nodeInfo ni in stg.points.Values)
			{
				foreach(nodeInfo ni2 in ni.Values)
				{
					ni2.color = Color.Pink;
				}
			}
			pic.Invalidate();
			LC lc = new LC(stg, this);
			ThreadStart ts = new ThreadStart(lc.comput);
			if(th != null && th.IsAlive)	th.Abort();
			th = new Thread(ts);
			th.Start();
		}
	}
}