没有合适的资源?快使用搜索试试~ 我知道了~
最短路(图论)1
需积分: 0 0 下载量 57 浏览量
2022-08-03
22:52:03
上传
评论
收藏 742KB PDF 举报
温馨提示
试读
17页
最短路(图论)1
资源详情
资源评论
资源推荐
Shortest Paths
Sample Problem: Overfencing [Kolstad & Schrijvers, Spring
1999 USACO Open]
Farmer John created a huge maze of fences in a field. He omitted two
fence segments on the edges, thus creating two ``exits'' for the maze.
The maze is a `perfect' maze; you can find a way out of the maze from
any point inside it.
Given the layout of the maze, calculate the number of steps required
to exit the maze from the `worst' point in the maze (the point that is
`farther' from either exit when walking optimally to the closest exit).
Here's what one particular W=5, H=3 maze looks like:
The Abstraction
Given:
A directed graph with nonnegative weighted edges
A path between two vertices of a graph is any sequence of
adjacent edges joining them
The shortest path between two vertices in a graph is the path
which has minimal cost, where cost is the sum of the weights of
edges in the path.
Problems often require only the cost of a shortest path not necessarily
the path itself. This sample problem requires calculating only the
costs of shortest paths between exits and interior points of the maze.
Specifically, it requires the maximum of all of those various costs.
Dijkstra's algorithm to find shortest paths in a weighted graph
Given: lists of vertices, edges, and edge costs, this algorithm `visits'
vertices in order of their distance from the source vertex.
Start by setting the distance of all notes to infinity and the
source's distance to 0.
At each step, find the vertex u of minimum distance that hasn't
been processed already. This vertex's distance is now frozen as
the minimal cost of the shortest path to it from the source.
Look at appending each neighbor v of vertex u to the shortest
path to u. Check vertex v to see if this is a better path than the
current known path to v. If so, update the best path
information.
In determining the shortest path to a particular vertex, this algorithm
determines all shorter paths from the source vertex as well since no
more work is required to calculate all shortest paths from a single
source to vertices in a graph.
Reference: Chapter 25 of [Cormen, Leiserson, Rivest]
Pseudocode:
# distance(j) is distance from source vertex to vertex j
# parent(j) is the vertex that precedes vertex j in any shortest path
# (to reconstruct the path subsequently)
1 For all nodes i
2 distance(i) = infinity # not reachable yet
3 visited(i) = False
4 parent(i) = nil # no path to vertex yet
5 distance(source) = 0 # source -> source is start of all paths
6 parent(source) = nil
7 8 while (nodesvisited < graphsize)
9 find unvisited vertex with min distance to source; call it v
ertex i
10 assert (distance(i) != infinity, "Graph is not connected")
11 visited(i) = True # mark vertex i as visited
# update distances of neighbors of i
12 For all neighbors j of vertex i
13 if distance(i) + weight(i,j) < distance(j) then
14 distance(j) = distance(i) + weight(i,j)
15 parent(j) = i
Running time of this formulation is O(V
2
). You can obtain O(E log V)
(where E is the number of edges and V is the number of vertices) by
using a heap to determine the next vertex to visit, but this is
considerably more complex to code and only appreciably faster on
large, sparse graphs.
Sample Algorithm Execution
Consider the graph below, whose edge weights can be expressed two
different ways:
Edge
Weight
(1, 3)
5
(1, 4)
8
(3, 4)
2
(3, 5)
3
(4, 2)
3
(4, 6)
7
(5, 2)
6
(2, 6)
2
1
2
3
4
5
6
1
0
0
5
8
0
0
2
0
0
0
3
6
2
3
5
0
0
2
3
0
4
8
3
2
0
0
7
5
0
6
3
0
0
0
6
0
2
0
7
0
0
Here is the initial state of the program, both graphically and in a table:
Distance to
Node
Visited
Source
Parent
1
T
0
nil
2
F
infinity
nil
3
F
infinity
nil
4
F
infinity
nil
5
F
infinity
nil
6
F
infinity
nil
Updating the table, node
1's neighbors include
nodes 3 and 4.
Distance to
Node
Visited
Source
Parent
1
T
0
nil
剩余16页未读,继续阅读
yxldr
- 粉丝: 20
- 资源: 327
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 基于python的机械设计实用计算器,可计算电动机,传动装置,V带轮,齿轮,轴,轴承的几何或者力,运动学参数数值+源码+开发文档
- 基于HTML +JavaScript的元旦倒计时代码.docx
- 【Unity资源免费分享】孩子益智小游戏unity 5x系列Baby Doll House Cleaning
- 【资源免费分享】集市游戏(uniyt案例)
- 数据整理结果 2023-12-7 192544 6.dta
- 5.22前端基础(2)
- 糖尿病风险因素分析数据
- matlab项目源码基于matlab的声源定位广义互相关算法的实现.zip
- 基于Go的Dory-Engine应用上云引擎命令行客户端设计源码
- dotnet-core-uninstall-1.7.521001 github上下载下来,从github下载不下来时,可以使用这
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0