登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

永远的绿岩

本期推荐:桂河大桥

 
 
 

日志

 
 
 
 

最短路径之Dijkstra算法程序(C#)  

2009-01-12 23:18:05|  分类: 3S |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

     赶时间做了比较粗糙的程序,程序平台VS.ENT,语言C#,所用图为前一篇文章的图。共享是最好的品格

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

namespace dj
{
    public partial class Form1 : Form
    {
        FindSortPath fsp = new FindSortPath(); //最短路径对象
        int  Combox1Select = 0;
        int  Combox2Select = 0;
        public Form1()
        {
            InitializeComponent();                
        }

        private void Form1_Load(object sender, EventArgs e)
        {           
                comboBox1.Items.Add("A");
                comboBox1.Items.Add("B");
                comboBox1.Items.Add("C");
                comboBox1.Items.Add("D");
                comboBox1.Items.Add("E");
                comboBox1.Items.Add("F");

                comboBox2.Items.Add("A");
                comboBox2.Items.Add("B");
                comboBox2.Items.Add("C");
                comboBox2.Items.Add("D");
                comboBox2.Items.Add("E");
                comboBox2.Items.Add("F");                       
        }

        private void comboBox1_SelectedIndexChanged(object sender, EventArgs e)
        {
            Combox1Select =1;           
        }

        private void comboBox2_SelectedIndexChanged(object sender, EventArgs e)
        {
            Combox2Select = 1;

        }

        private void button1_Click(object sender, EventArgs e)
        {
            int m = 2000;
            int[,] G ={     {m,6,3,m,m,m},
                            {6,m,2,5,m,m},
                            {3,2,m,3,4,m},
                            {m,5,3,m,2,3},
                            {m,m,4,2,m,5},
                            {m,m,m,3,5,m}
                       };

            int glength = (int)Math.Sqrt(G.Length);//算出顶点数
            int maxsize = 1000;//当权值超过1000时说明没有路径  

            if (Combox1Select == 1 && Combox2Select == 1&&comboBox1.SelectedIndex !=comboBox2.SelectedIndex)
            {
                fsp.vo = comboBox1.SelectedIndex;  //源点
                fsp.vi = comboBox2.SelectedIndex;  //终点
                fsp.OneToOneSP(G, glength, maxsize);

                string str = "";
                int[] temp = new int[fsp.ShortPath.Length];
                for (int i = 0; i < fsp.ShortPath.Length; i++)
                {
                    str=str + comboBox1.Items[fsp.ShortPath[i]].ToString()+" " ;
                }                  
                textBox1.Text = str;
                textBox2.Text = fsp.ShortDist.ToString();
            }
            else
                MessageBox.Show("请选择起点和终点");

        }

        private void button2_Click(object sender, EventArgs e)
        {
            textBox1.Text = "";
            textBox2.Text = "";
        }

        private void button3_Click(object sender, EventArgs e)
        {
            Application.Exit();
        }

    }

    public class FindSortPath
    {
        public int ShortDist = 0; //最短路径长度
        public int vo;        //起点
        public int vi;        //终点
        public int[] ShortPath; //最短路径


        public FindSortPath()
        {
        }


        //从某一源点出发,找到到某一结点的最短路径
        public void OneToOneSP(int[,] G, int n, int MaxSize)
        {
            bool[] s = new bool[n];       //true时表示已找到最短路径 false时表示未找到          
            int[] dist = new int[n];      //保存从源点到终点vi的目前最短路径长度
            int[] prev = new int[n];      //保存从源点到终点vi当前最短路径中的前一个顶点的编号,它的初值为原点vo(vo到vi有边时),或者-1(vo到vi无边时)
            int mindis;                   //最小距离临时变量
            int u;                        //临时结点,记录当前正计算结点           

            //初始结点信息
            for (int i = 0; i < n; i++)
            {
                s[i] = false;            //s[]表置空
                dist[i] = G[vo, i];      //距离初始化
                if (dist[i] > MaxSize)   //路径初始化
                    prev[i] = -1;
                else
                    prev[i] = vo;
            }
            s[vo] = true;   //将源点编号放入s表中 
            prev[vo] = 0;   //因为一共有n个顶点,而且prev的个数是n,所以应把初始顶点的前一点设为0,从而凑够n   

            //主循环
           
            for (int i = 0; i < n; i++)
            {
                u = -1;                        //初始化中间顶点
                mindis = MaxSize;              //假设点与点之间的距离在未知的情况下为无穷                           
                for (int j = 0; j < n; j++)    //选取不在s中且具有最小距离的顶点u
                {
                    if (!s[j] && dist[j] < mindis)
                    {
                        u = j;
                        mindis = dist[j];
                    }
                }
                s[u] = true;   //将顶点u加入s中


                if (vi == u)   //当找到vi时跳出循环,没找到时继续找
                {
                    break;
                }
                else
                {
                    for (int j = 0; j < n; j++)
                        if (s[j]==false )
                            if (G[u,j]<MaxSize && mindis + G[u, j] < dist[j])  //以u为新考虑的中间点,修改不在s中各顶点的距离;若从源点vo到不在s中的顶点的距离(经过顶点u)比原来距离(不经过顶点u)短,则修改不在s中的顶点的距离值,修改后的距离值为顶点u的距离加上边<j,u>上的权。
                            {
                                dist[j] = mindis + G[u, j];
                                prev[j] = u;
                            }
                }             
            }           

            //输出路径结点
            int e = vi;
            int step = 0;
            int[] path = new int[n];
            path[0] = vi;     //将vi放进去      
            while (e != vo)   //从后面往前面找vi的最短路径
            {
                step++;              
                path[step] = prev[e];
                e = prev[e];              
            }
         
            for (int i = step; i > step / 2; i--)//将顺序颠倒,记录从源点到终点的编号
            {
                int temp = path[step - i];
                path[step - i] = path[i];
                path[i] = temp;
            }           

            //将临时路径表复制到属性ShortPath
            ShortPath = new int[step + 1];
            for (int i = 0; i <= step; i++)
            {
                ShortPath[i] = path[i];
            }

            ShortDist = dist[vi];//输出最短路径长度
        } 
    }
}

 

参考文献 

[1] 李春葆,数据结构教程,清华大学出版社,2005年1月第1版

[2]Dijkstra 最短路径算法C#实现http://blog.csdn.net/chaihuo/archive/2007/10/29/1853624.aspx

 

  评论这张
 
阅读(4411)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018