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

namespace shtpath
{
	/// <summary>
	/// Form1 的摘要說明。
	/// </summary>
	public class Form1 : System.Windows.Forms.Form
	{
		private System.Windows.Forms.ComboBox comboBox1;
		private System.Windows.Forms.ComboBox comboBox2;
		private System.Windows.Forms.Label label1;
		private System.Windows.Forms.Label label2;
		private System.Windows.Forms.RichTextBox richTextBox1;
		public int startID;
		public int endID;
		private System.Windows.Forms.Button button1;
		public int [,]map=new int[,]{{0,3,4,0,0,0},
									 {3,0,0,2,5,0},
									 {0,0,0,0,1,0},
									 {0,0,0,0,0,4},
									 {0,0,1,0,0,6},
									 {0,0,0,4,0,0}};
		public ArrayList open;
		public ArrayList closed;
			/// <summary>
			/// 必需的設計器變量。
			/// </summary>
			private System.ComponentModel.Container components = null;

		public Form1()
		{
			//
			// Windows 窗體設計器支持所必需的
			//
			InitializeComponent();

			//
			// TODO: 在 InitializeComponent 調用后添加任何構造函數代碼
			//
		}

		/// <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.comboBox1 = new System.Windows.Forms.ComboBox();
			this.comboBox2 = new System.Windows.Forms.ComboBox();
			this.label1 = new System.Windows.Forms.Label();
			this.label2 = new System.Windows.Forms.Label();
			this.richTextBox1 = new System.Windows.Forms.RichTextBox();
			this.button1 = new System.Windows.Forms.Button();
			this.SuspendLayout();
			// 
			// comboBox1
			// 
			this.comboBox1.Items.AddRange(new object[] {
														   "1",
														   "2",
														   "3",
														   "4",
														   "5",
														   "6"});
			this.comboBox1.Location = new System.Drawing.Point(56, 8);
			this.comboBox1.Name = "comboBox1";
			this.comboBox1.Size = new System.Drawing.Size(88, 20);
			this.comboBox1.TabIndex = 1;
			this.comboBox1.SelectedIndexChanged += new System.EventHandler(this.comboBox1_SelectedIndexChanged);
			// 
			// comboBox2
			// 
			this.comboBox2.Items.AddRange(new object[] {
														   "1",
														   "2",
														   "3",
														   "4",
														   "5",
														   "6"});
			this.comboBox2.Location = new System.Drawing.Point(208, 8);
			this.comboBox2.Name = "comboBox2";
			this.comboBox2.Size = new System.Drawing.Size(88, 20);
			this.comboBox2.TabIndex = 2;
			this.comboBox2.SelectedIndexChanged += new System.EventHandler(this.comboBox2_SelectedIndexChanged);
			// 
			// label1
			// 
			this.label1.Location = new System.Drawing.Point(16, 8);
			this.label1.Name = "label1";
			this.label1.Size = new System.Drawing.Size(32, 16);
			this.label1.TabIndex = 3;
			this.label1.Text = "起點";
			// 
			// label2
			// 
			this.label2.Location = new System.Drawing.Point(168, 8);
			this.label2.Name = "label2";
			this.label2.Size = new System.Drawing.Size(32, 16);
			this.label2.TabIndex = 4;
			this.label2.Text = "終點";
			// 
			// richTextBox1
			// 
			this.richTextBox1.Location = new System.Drawing.Point(0, 40);
			this.richTextBox1.Name = "richTextBox1";
			this.richTextBox1.Size = new System.Drawing.Size(384, 264);
			this.richTextBox1.TabIndex = 5;
			this.richTextBox1.Text = "";
			// 
			// button1
			// 
			this.button1.Location = new System.Drawing.Point(320, 8);
			this.button1.Name = "button1";
			this.button1.Size = new System.Drawing.Size(56, 23);
			this.button1.TabIndex = 6;
			this.button1.Text = "查詢";
			this.button1.Click += new System.EventHandler(this.button1_Click);
			// 
			// Form1
			// 
			this.AutoScaleBaseSize = new System.Drawing.Size(6, 14);
			this.ClientSize = new System.Drawing.Size(384, 301);
			this.Controls.Add(this.button1);
			this.Controls.Add(this.richTextBox1);
			this.Controls.Add(this.label2);
			this.Controls.Add(this.label1);
			this.Controls.Add(this.comboBox2);
			this.Controls.Add(this.comboBox1);
			this.Name = "Form1";
			this.Text = "最短路徑演示";
			this.Load += new System.EventHandler(this.Form1_Load);
			this.ResumeLayout(false);

		}
		#endregion

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

		private void Form1_Load(object sender, System.EventArgs e)
		{
			richTextBox1.Clear();
			closed=new ArrayList(50);
			open=new ArrayList(50);
			closed.Clear();
			open.Clear();
		}
		private void FindPath(int startno,int endno)
		{
			int j,k,k1,k2;
			int min=100;
			int row,colum;
			node current=new node();//closed中最后進入的點為當前結點
			node near=new node();//在open中距離起點最近的結點
			node next=new node();//待擴展的結點
			//起點初始化操作
			node n=new node();
			n.nodeID=startno;
			n.dTotalLong=0;
			n.lastNodeID=0;
			closed.Add(n);
			int num=closed.Count;
			while(((node)closed[num-1]).nodeID!=endno)
			{
				current.nodeID=((node)closed[num-1]).nodeID;
				current.dTotalLong=((node)closed[num-1]).dTotalLong;
				current.lastNodeID=((node)closed[num-1]).lastNodeID;
				row=current.nodeID-1;
				//擴展當前結點的后繼結點
				for(colum=0;colum<6;colum++)
				{
					if(map[row,colum]!=0)
					{
						next.nodeID=colum+1;
						next.lastNodeID=current.nodeID;
						next.dTotalLong=current.dTotalLong+map[row,colum];
						for(k1=0;k1<closed.Count;k1++)
						{
							if(next.nodeID==((node)closed[k1]).nodeID)//表明在closed隊列中
								break;
						}
							if(k1==closed.Count)//表明不在closed隊列中
							{
								//判斷該后繼結點是否在open隊列中
								for(k2=0;k2<open.Count;k2++)
								{
									if(next.nodeID==((node)open[k2]).nodeID)//在open中
									{
										if(next.dTotalLong<((node)open[k2]).dTotalLong)
										{	
											((node)open[k2]).dTotalLong=next.dTotalLong;
											((node)open[k2]).lastNodeID=next.lastNodeID;
											break;
										}
									}
								}
								if(k2==open.Count)
								{
									open.Add(next);
								}
							}
					}
				}
				//在open隊列中尋找離起點最近的點
				for(j=0;j<open.Count;j++)
				{
					if(min>((node)open[j]).dTotalLong)
					{
						min=((node)open[j]).dTotalLong;
						near.nodeID=((node)open[j]).nodeID;
						near.lastNodeID=((node)open[j]).lastNodeID;
						near.dTotalLong=((node)open[j]).dTotalLong;
						//k=j;
					}
				}
				closed.Add(near);
				num=closed.Count;
				for(j=0;j<open.Count;j++)
					if(near.nodeID==((node)open[j]).nodeID)
						break;
				//((node)open[j]).dTotalLong=20;
				open.RemoveAt(j);
			}
			
		}

		private void button1_Click(object sender, System.EventArgs e)
		{
			richTextBox1.Clear();
			this.FindPath(startID,endID);
			int startno;
			int i;
			startno=endID;
			while(startno!=startID)
			{
				for(i=0;i<closed.Count;i++)
				{
					if(startno==((node)closed[i]).nodeID)
					{
						richTextBox1.Text="-->"+startno.ToString()+richTextBox1.Text;
						startno=((node)closed[i]).lastNodeID;
					}
				}
			}
			richTextBox1.Text=startID.ToString()+richTextBox1.Text;
		}

		private void comboBox1_SelectedIndexChanged(object sender, System.EventArgs e)
		{
			startID=int.Parse(comboBox1.Text);
		}

		private void comboBox2_SelectedIndexChanged(object sender, System.EventArgs e)
		{
			endID=int.Parse(comboBox2.Text);
		}
	}
}