麻省理工学院：《算法导论》（英文版） Lecture 18 Prof erik demaine

文档信息

资源类别：文库
文档格式：PDF
文档页数：25
文件大小：166.67KB
团购合买：点击进入团购

内容简介

Negative-weight cycles Recall: If a graph G=(V, E) contains a negative weight cycle then some shortest paths may not exist

刷新页面文档预览

Introduction to algorithms 6.046J/18,401J/SMA5503 Lecture 18 Prof erik demaine

Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 18 Prof. Erik Demaine

Negative-weight cycles Recall: If a graph G=(V, E) contains a negative weight cycle then some shortest paths may not exist Example: <0 Bellman-Ford algorithm: Finds all shortest-pat lengths from a sources e y to all ve yor determines that a negative-weight cycle exists c 2001 by Charles E Leiserson Introduction to Algorithms Day 31 L18.2

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31 L18.2 Negative-weight cycles Recall: If a graph G = (V, E) contains a negativeweight cycle, then some shortest paths may not exist. Example: uu vv … < 0 Bellman-Ford algorithm: Finds all shortest-path lengths from a source s ∈ V to all v ∈ V or determines that a negative-weight cycle exists

Bellman- Ford algorithm ds]du+ w(u, v) relaxation then dlv]←+w(al,y)∫step for each edge(l2y)∈E do if dv>du+w(u, v) then report that a negative-weight cycle exists At the end dv=8(s, v). Time=O(VE) c 2001 by Charles E Leiserson Introduction to Agorithms Day31L18.3

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31 L18.3 Bellman-Ford algorithm d[s] ← 0 for each v ∈ V – {s} do d[v] ← ∞ for i ← 1 to |V| – 1 do for each edge (u, v) ∈ E do if d[v] > d[u] + w(u, v) then d[v] ← d[u] + w(u, v) for each edge (u, v) ∈ E do if d[v] > d[u] + w(u, v) then report that a negative-weight cycle exists initialization At the end, d[v] = δ(s, v). Time = O(VE). relaxation step

Example of bellman-Ford AB C E B 0 E D c 2001 by Charles E Leiserson Introduction to Agorithms Day 31 L18.4

Example of Bellman-Ford AB C E B 2 000 E D c 2001 by Charles E Leiserson Introduction to Agorithms Day 31 L18.5

Example of bellman-Ford AB C E B 000 E)0-14∞ D 4 c 2001 by Charles E Leiserson Introduction to Agorithms Day 31 L18.6

Example of bellman-Ford AB C E B 000 E)0-14∞ 0-12∞ D c 2001 by Charles E Leiserson Introduction to Agorithms Day 31 L18.7

Example of bellman-Ford AB C E B 000 E)0-14∞ 0-12∞ D c 2001 by Charles E Leiserson Introduction to Agorithms Day 31 L18.8

Example of bellman-Ford AB C E B人、2 000 E)0-14∞ 0-12∞ D 0-12∞1 c 2001 by Charles E Leiserson Introduction to Agorithms Day 31 L18.9

Example of bellman-Ford AB C E B 000 E 14∞ 12∞ D 0000 12∞1 c 2001 by Charles E Leiserson Introduction to Agorithms Day 31 L18.10

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31 L18.10 ∞1 0 –1 2 1 1 –1∞ Example of Bellman-Ford AA BB EE CC DD –1 4 1 2 –3 2 5 3 0 2 0 –1 2 ∞ ∞ 0 –1 ∞∞∞ ABCDE 0 ∞∞∞∞ 0 –1 4 ∞∞ 1 0 –1 2 ∞ 1

共25页，试读已结束，阅读完整版请下载

刷新页面下载完整文档

VIP每日下载上限内不扣除下载券和下载次数；
按次数下载不扣除下载券；
注册用户24小时内重复下载只扣除一次；
顺序：VIP每日次数-->可用次数-->下载券；

点击下载完整版文档（PDF）