单源最短路径解析-阿里云开发者社区

开发者社区> kiba518> 正文

单源最短路径解析

简介: 首先说下算法原理: 1,设0为源点,建立两个集合S,T,S保存节点0,T集合保存节点1,2,3,4。(S,T是官方定义名称,个人理解S应该是source的缩写,T是target的缩写,看了英文是不是就明白点了) 2,先找出0到其他点最短的点,0到1等于10,即0-1为最短。
+关注继续查看

首先说下算法原理:

1,设0为源点,建立两个集合S,T,S保存节点0,T集合保存节点1,2,3,4。(S,T是官方定义名称,个人理解S应该是source的缩写,T是target的缩写,看了英文是不是就明白点了)

2,先找出0到其他点最短的点,0到1等于10,即0-1为最短。那么将1添加进S,将1从T中删除。

3,修正路径,这是个难点,怎么修改呢,我举最简单的例子,那就是直接在图上修改。修正路径要修正的是0到其他节点的路径长度,先看下图,

0-1=10

0-2=正无穷,因为0直接到不了2

0-3=30

0-4=100

当我们在S集合中增加了节点1,那么0到其他节点的方式就多了一个,比如0-2,就不在是正无穷,他可以通过1到达,所以0-2=60

那么0-4=100,当0通过1在到达4,结果是0-1-4=10加正无穷,因为1到达不了4,所以10+正无穷就大于100,所以0-4还是100,0-3同理,10+正无穷>30,因此0-3还是30。

1添加进集合S后,在添加次短的节点,因为1是最短的,添加完最短的添加次短的。

现在是0到各节点的路径是:

0-1=10

0-2=60

0-3=30

0-4=100

这里0-3是最短的,因此S集合添加节点3,同样移除T中,3。

添加完3后,再修正路径,因为1已经添加过了所以不在修改1。那么添加2,0-2在上面已经被修正成60了,现在看0-3-2,它等50,小于60,所以0-2再次修正,等于50。0-3不修正,因为是当前选则的路径。接着修改0-4,0-4初始等于100,现在0-3-4等于160,大于100,所以0-4仍然等于100

0-1=10

0-2=50

0-3=30

0-4=100

接着再找最短的,1,3已经选过了,现在最短的是2,0-2=50,通过2在修正,13已经选过不在修正,只修正4,即0-2-4=60(具体流向是0-3-2-4),小于0-4=100,因此修正0-4=60。

最后将4从T中取出添加进S,因为123都已经使用,4不在修正,方法结束,即T为空就结束。

那么0到各点的最短路径为

0-1=10

0-2=50

0-3=30

0-4=60

 

 

将上面的算法写成代码如下:

但在学习代码前,首先要理解数组weight是什么,数组weight翻译出来是

第一行 {0,3,2000,7,9999999}

A——>A 宽度(权值)0 自己到自己自然是0

A——>B 宽度(权值)3

A——>C 宽度(权值)2000

A——>D 宽度(权值)7

A——>E 宽度(权值)9999999即无限大,即 到达不了E 

 

第二行   {3,0,4,2,9999999},

B——>A 宽度(权值)3

B——>B 宽度(权值)0 B-B

B——>C 宽度(权值)4

B——>D 宽度(权值)2

B——>E 宽度(权值)9999999 即无限大,即到达不了E 

 

第三行    {9999999,4,0,5,6},

C——>A 宽度(权值)9999999 即无限大 ,即 到达不了A

C——>B 宽度(权值)4

C——>C 宽度(权值)0 C-C

C——>D 宽度(权值)5

C——>E 宽度(权值)6 

 

第四行      {7,2,5,0,4},

D——>A 宽度(权值)7

D——>B 宽度(权值)2

D——>C 宽度(权值)5

D——>D 宽度(权值)0 D-D

D——>E 宽度(权值)4

 

第五行      {9999999,9999999,4,6,0}

E——>A 宽度(权值)9999999即无限大,即 到达不了A

E——>B 宽度(权值)9999999即无限大,即 到达不了B

E——>C 宽度(权值)4

E——>D 宽度(权值)6

E——>E 宽度(权值)0 E-E

以下为C#代码 可以运行

 public class Dijkstra
    {
        public static void Excute()
        {
            int[][] weight = new int[][]
            {
              new int[] {0,3,2000,7,9999999},
              new int[] {3,0,4,2,9999999},
              new int[] {9999999,4,0,5,6},
              new int[] {7,2,5,0,4},
              new int[] {9999999,9999999,4,6,0}

             };
            int[] path = Dijsktra(weight, 0);
            for (int i = 0; i < path.Length; i++)

                Console.WriteLine(path[i] + "  ");

        }

        public static int[] Dijsktra(int[][] weight, int start)
        {
            //接受一个有向图的权重矩阵,和一个起点编号start(从0编号,顶点存在数组中) 
            //返回一个int[] 数组,表示从start到它的最短路径长度 
            int n = weight.Length;      //顶点个数 
            int[] shortPath = new int[n];   //存放从start到其他各点的最短路径 

            int[] visited = new int[n];     //标记当前该顶点的最短路径是否已经求出,1表示已求出 

            //初始化,第一个顶点求出
            shortPath[start] = 0;
            visited[start] = 1;
            for (int count = 1; count <= n - 1; count++)        //要加入n-1个顶点
            {
                int k = -1; //选出一个距离初始顶点start最近的未标记顶点
                int dmin = 1000;
                for (int i = 0; i < n; i++)
                {
                    if (visited[i] == 0 && weight[start][i] < dmin)
                    {
                        dmin = weight[start][i];

                        k = i;
                    }
                }
                //将新选出的顶点标记为已求出最短路径,且到start的最短路径就是dmin 
                shortPath[k] = dmin; 
                visited[k] = 1; 

                //以k为中间点想,修正从start到未访问各点的距离  
                for (int i = 0; i < n; i++)
                {
                    if (visited[i] == 0 && weight[start][k] + weight[k][i] < weight[start][i])
                        weight[start][i] = weight[start][k] + weight[k][i];

                }

            } 
            return shortPath; 
        } 
    }

 

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
10092 0
硬解析和物理读取与软解析和逻辑读取
参考:http://www.cnblogs.com/chinhr/archive/2009/03/14/1412100.html 001 预备知识 ·Recursive Calls:有时为了执行用户发出的一条SQL语句,Oracle必须执行额外的语句。
636 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
10886 0
回调函数中JSON对象的解析方式
惯例: 我是温浩然: 先说代码: &lt;div class="modal-body"&gt; &lt;span style="white-space:pre"&gt; &lt;/span&gt;            &lt;!-- &lt;iframe src="http://file-server.erzao.org/file-server/video/select/61?
1806 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13893 0
一道归并排序题的解析
设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},请写出按二路归并方法对该序列进行一趟扫描后的结果为 ()。
572 0
+关注
kiba518
天下多少有情事,满眼尽是无奈人。
34
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载