How To Get Min-Cost Between two points in graph (Dijkstra’s algorithm)

作者:无名 - 软件应用 -

How To Get Min-Cost Between twopoints in graph

(Dijkstra’s algorithm)

Now See This Graph :

How To Get Min-Cost Between two points in graph (Dijkstra’s algorithm)_第1张图片

which is just like asubway map .

Now Question is :

how to calculate fromA to (B,C,D,E,F,G,H,I,J) min cost

Now Let's go through Dijkstra's algorithm.

I will start follow these steps :

Step 1:

Take point from (A,B,C,D,E,F,G,H,I,J) .

Step 2:

find out the points it can reach ,save as reached-points

Step 3:

update the reached-points distance by the new dist if it is smaller than the old value

ok , now take A, and we can see ,A can reach B,C,D

How To Get Min-Cost Between two points in graph (Dijkstra’s algorithm)_第2张图片

Now I take B. B Can Reach D,E. SoI need to update the value for D,E


How To Get Min-Cost Between two points in graph (Dijkstra’s algorithm)_第3张图片

As 4+3 < 8 . sothe value for D updated to 7.

Next ,Take C. C canreach D,F ,So I Need to update D,F values

How To Get Min-Cost Between two points in graph (Dijkstra’s algorithm)_第4张图片



Next ,Take D , D CanReach B,C,E,F,G , I Need to update them relatively .

But Can See ,D'svalue is 6 ,gather than B(4) and C(5) ,so no need update for B,C.

How To Get Min-Cost Between two points in graph (Dijkstra’s algorithm)_第5张图片


Next, Take E. whichCan Reach B,D,G,H

E(15)>B(4) ,E(15) > D(6), no updating.

E(15) + 6 >G(16),So no updating for G(16).

How To Get Min-Cost Between two points in graph (Dijkstra’s algorithm)_第6张图片


Next ,F .Can reach C,D,G,I

How To Get Min-Cost Between two points in graph (Dijkstra’s algorithm)_第7张图片


For C,D .

F(10) > D(6) ,F(10) > C(5) , so no updating .

Ok ,Next G. Whichcan reach D,E,F,H,I,J

G(15)>=E(15),G(15)>D(6),G(15) > F(10) .So No need update .now let's see how about H,I,J


How To Get Min-Cost Between two points in graph (Dijkstra’s algorithm)_第8张图片

G(15) + 3 < H(25)

G(15) + 5 <I(21)

J(30) is new added

so update them.

Next ,Take H. whichcan reach E,G,J

H(18) >E(15)=G(15) .No updating .

H(18) + 14 > J(30), also no updating .


How To Get Min-Cost Between two points in graph (Dijkstra’s algorithm)_第9张图片

Next ,Take I. CanReach F,G,J

I(20) >F(10),I(20)>G(15) , no updating

Let's see J

How To Get Min-Cost Between two points in graph (Dijkstra’s algorithm)_第10张图片


I(20) + 8 < J(30)

so update J(30)-> J(28)

Last ,Add J ,CanReach G,H,I

How To Get Min-Cost Between two points in graph (Dijkstra’s algorithm)_第11张图片


but J(28) >G(15),

J(28) > H(18),

J(28) > I(20)

so no updating .

以上就是由(IT人知识库http://www.itpeo.net/15315/3488890.html)本站为大家整理





标签
rfedfre

深入解读Quartz及应用

一、Quartz基本概念   Quartz 是 OpenSymphony开源组织在任务调度领域的... ...

rfedfre

Ubuntu9.10(Karmic) 安装Chandler

Chandler是一个比较出名的PIM软件,用来作工作计划很不错。我是阅读了《梦断代码》才用上他的。最近从XP转到Ubu... ...

rfedfre

Use Axis2.x(WebService)- 01

  前言 笔者首先在此向大家简单介绍下与此篇博文相关的一些概念及理论,但愿大家有心情和时间听笔者废... ...

rfedfre

Android源代码加入SDK,在程序中查看android源代码

本文主要展示如何利用Android源代码,介绍一下Android源代码加入SDK,就可以按F3查看类了。 当... ...

rfedfre

iredmail使用tips

DNS DNS记录,需要你到你的域名托管商那里进行设置或者你自己管理DNS服务器。不少域名托管商不支持txt记录或... ...

rfedfre

亲历2012百度开发者大会

今天专门请了一天假,去参加百度开发者大会。看图说话。 上午的内容包括李彦宏的演讲——百度云时代,其它的话题也大都密... ...

rfedfre

阿福播放器2.0

阿福播放器(末尾下载) 下载地址:http://www.eoemarket.com/apps/9348 ... ...

rfedfre

常用思科设备图标(JPG+矢量图)

常用思科设备图标 在制作网络拓扑图示时我们利用MS Visio或亿图图示等制图软件自带的网络设备绘制拓扑图感觉提供的... ...

rfedfre

第十章 会话管理——《跟我学Shiro》

  目录贴: 跟我学Shiro目录贴   Shiro提供了完整的企业级会... ...

rfedfre

"百度推荐引擎实践:策略篇"分享总结

概述: 此分享是关于百度推荐引擎实践:策略篇简介 汇总点: 1.搜索与推荐是被动和主动的关系; 2.推... ...

rfedfre

Android开发中怎么使用绘制图表

本文原文发表在http://tech.it168.com/a2011/0603/1200/000001200313.sh... ...

rfedfre

有意的建站系统资料

http://www.mmpcms.com/bdclkid=rP4_J2R4sdT1AWGsteJ3FGtNxTPK0g... ...

rfedfre

tcpcopy架构复杂应用实例

在线系统介绍: 假设我们有在线机器A,在线机器B,在线机器C三台服务器,其中在线机器A,上面运行nginx(8... ...

rfedfre

java 访问控制符学习笔记

1.私有权限(private) private可以修饰数据成员,构造方法,方法成员,不能修饰类(此处指外部类,... ...

rfedfre

Oracle 索引结构、内部管理

Oracle 索引结构、内部管理 摘要:本文对B树索引的结构、内部管理等方面做了一个全... ...

rfedfre

系统主数据管理之供应商(Supplier)五 供应商的“接收”属性(Receiving)

该属性仅在“供应商层”可设置,为所有的Site层所共用,如下图51所示:   不过,这里的大多数属性设置,... ...

rfedfre

系统主数据管理之供应商(Supplier)六 供应商Site层的“一般”属性

如下图52所示,供应商Site层与“供应商层”的“一般”Tab页内容差别较大。Site层的“地点用途”中,“支付”如果未... ...

rfedfre

深刻理解JavaScript基于原型的面向对象

  主题一、原型   一、基于原型的语言的特点... ...

rfedfre

Task(Activity栈) 详解

什么是Android Application? 简单来说,一个apk文件就是一个Applicatio... ...

rfedfre

action里面的值显示到JSP页面

今天在项目中,遇到一个问题,就把action里面执行的结果传到jsp页面上,在jsp页面上显示。 解决办法:把执行... ...