August 2017
Intermediate to advanced
360 pages
8h 35m
Chinese
Content preview from 算法技术手册（原书第2 版）
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
226
｜
第
8
章
虽然不清楚
Ford-Fulkerson
算法能否可用于解决这个问题，但是我们可以先构造一个图
G
，将新的源顶点
s
0
连接两个工厂顶点（
v
1
和
v
2
），并将两个消费顶点（
v
3
和
v
4
）连接
到新的汇点
t
5
。为了节省空间，图中忽略了源顶点和汇点。在图
8-7
的左边，我们使用
Edmonds-Karp
算法证明了可以满足消费者的所有需求，但是每天的运输费用是
3600
美元。图中还显示了在
Ford-Fulkerson
算法中的
4
次迭代中增广路径所带来的影响（在
每次迭代更新完边的流量后，我们会将该流量值标记为灰色）。
这是能够得到的最小费用吗？在图
8-7
的右边，我们给出了使用
ShortestPath-Array
作
为搜索策略的
Ford-Fulkerson
算法的执行过程，具体算法可以参见例
8-6
。我们可以看
到第一条增广路径的寻找过程是利用了最小费用的航运率。同样，
Shortest-PathArray
方法只有在芝加哥（
v
1
）到休斯敦（
v
3
）没有可以满足用户需求的其他路线时，才会选
择费用较高的货运路线。事实上，如果这种情况发生，我们会看到增广路径减少了华盛
顿特区（
v
2
）和休斯敦（
v
3
）之间的流量以及华盛顿特区（
v
2
）和波士顿（
v
4
）之间的流量。
8.5 最小费用流
要解决最小费用流问题，需要构造一个流网络图，并确保它满足之前讨论过的限制条件：
容量限制、流量守恒以及反对称性。此外，图还要保证如下两个条件：供应满足和需求
满足。这些术语常常应用在金融背景中，类似于电器工程中的发射端和接收端。
供应满足
对每个源顶点 ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.