構造類并實作最短路徑方法

在前面的C#編程中，我們已經完成了諸如遍歷、最小生成樹等許多方法，這個類已經可以完成諸如鄰接矩陣輸入、頂點矩陣輸入問題，這個類在Graph2.cs中，
現在，我們新建立一個WINDOWS工程，位置在C#\Dijstra檔案夾下，并把Graph.cs復制到該檔案夾下，并讓你的工程參考它，

Graph.cs及最短路徑Dijstra方法如下：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows.Forms;

class Graph
{
    private int[,] A;
    private string[] V;
    private int[] Visited;
    private TreeNode[] T;
    private int num;
    private int ConnComp;
    public Graph(int n)
    {
        int i;
        num = n;
        A = new int[n, n];
        V = new string[n];
        T = new TreeNode[n];
        Visited = new int[n];
        for (i = 0; i < n; i++)
        {
            T[i] = new TreeNode();
            Visited[i] = 0;
        }
        ConnComp = 0;
    }
    public int[,] Arc
    {
        set { A = value; }
        get { return A; }
    }
    public string[] Vertex
    {
        set { V = value; }
        get { return V; }
    }
    public int ConnectComponent
    {
        get { return ConnComp; }
    }
 
 
    public void Dijstra(int vStart,int NO,int[] D,int[] iPath)
    {
        int i, j, MinDis, u;
        for(i=0;i<num;i++)
        {
            D[i]=A[vStart,i];
            Visited[i]=0;
        }
        Visited[vStart] = 1; u = 0;
        for(i=0;i<num;i++)
        {
            MinDis=NO; 
            for(j=0;j<num;j++)
                if(Visited[j]==0&&D[j]<MinDis)
                {
                    MinDis=D[j];u=j;
                }
            if(MinDis==NO) return;
            Visited[u]=1;
            for(j=0;j<num;j++)
            {
                if(Visited[j]==0&&A[u,j]<NO&&u!=j)
                    if ((D[u] + A[u, j]) < D[j])
                        {
                            D[j] = D[u] + A[u, j];
                            Visited[j] = 0;
                            iPath[j] = u;
                        }
            }
        }
    }
   
}

設計界面撰寫程式測驗新的Graph類

打開VS集成開發環境，創建一個winform專案，在Form1中添加一個listBox1控制元件、兩個button控制元件，button1控制元件Text屬性修改成“Dijstra最短路”，button2控制元件屬性Text修改成“結束”，滑鼠雙擊button1控制元件進入編程環境，開始撰寫測驗最短路的程式，

Dijstra最短路徑：

Floyd最短路徑：

我們沒必要把程式設計的太復雜，僅僅用一個固定的圖說明結果即可，真正涉及到各種圖都計算最短路徑的作業，我們放在ASP.NET系統下，所以整個測驗程式就是：

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace Dijstra
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void button1_Click(object sender, EventArgs e)
        {
            Graph G = new Graph(6);
            int[] D = new int[6];
            int[] iPath = new int[6];
            string[] V = { "V0", "V1", "V2", "V3", "V4", "V5" };
            int[,] A ={
                        {1000, 1000,   10, 1000,   30,  100},
                        {1000, 1000,    5, 1000, 1000, 1000},
                        {1000, 1000, 1000,   50, 1000, 1000},
                        {1000, 1000, 1000, 1000, 1000,   10},
                        {1000, 1000, 1000,   20, 1000,   60},
                        {1000, 1000, 1000, 1000, 1000, 1000}
                    };
            G.Arc = A;
            G.Dijstra(0, 1000, D, iPath);
            listBox1.Items.Clear();
            string st0 = "", st1 = "", vs = "";
            for (int i = 0; i < 6; i++)
            {
                vs = vs + V[i] + '\t';
                st0 = st0 + D[i].ToString() + "\t";
                st1 = st1 + iPath[i].ToString() + "\t";
            }
            listBox1.Items.Add(vs);
            listBox1.Items.Add(st0);
            listBox1.Items.Add(st1);
        }

        private void button2_Click(object sender, EventArgs e)
        {
            Graph G = new Graph(3);
            string[] V = { "V0", "V1", "V2" };
            int[,] fPath= new int[3, 3]; 
            int[,] A ={
                         {1000,    4,      11},
                         {   6,    1000,    2},
                         {   3,    1000, 1000}
                     };
            G.Arc = A;
            G.Vertex = V;
            
            listBox1.Items.Clear();  
            string st0 = "", vs = "";
            A = G.Arc; 
            for (int i = 0; i < 3; i++)
                vs = vs + V[i] + '\t';
            listBox1.Items.Add(vs);
            for (int i = 0; i < 3; i++)
            {
                st0 = "";
                for (int j = 0; j < 3; j++)
                    st0 = st0 + A[i, j].ToString() + '\t';
                listBox1.Items.Add(st0);
            }
            listBox1.Items.Add("路徑：");
            for (int i = 0; i < 3; i++)
            {
                st0 = "";
                for (int j = 0; j < 3; j++)
                    st0 = st0 + fPath[i, j].ToString() + '\t';
                listBox1.Items.Add(st0);
            }
        }

        private void button3_Click(object sender, EventArgs e)
        {
            this.Close();
        }
    }
}

注意這里的結果顯示是在listBox1控制元件中，由于僅僅是數字，所以在第18行轉換成字串的行、添加在listBox1控制元件中即可，

本次測驗程序非常簡單，程式也很簡單，但不代表我們的程式僅僅是這么使用，真正意義上該如何使用這個類，見《Asp站點配置.doc》，在這個講義里會讓大家知道C#程式是怎么使用的，

思考題：

1. 在Graph類中補充Floyd最短路計算方法；
2. 測驗你的Floyd方法，