构造类并实现最短路径方法

在前面的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方法。