一、 迪杰斯特拉算法思想

Dijkstra算法主要針對(duì)的是有向圖的單元最短路徑問(wèn)題，且不能出現(xiàn)權(quán)值為負(fù)的情況！Dijkstra算法類似于貪心算法，其應(yīng)用根本在于最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)。

最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)：

如果P(i,j)={Vi…Vk…Vs…Vj}是從頂點(diǎn)i到j(luò)的最短路徑，k和s是這條路徑上的一個(gè)中間頂點(diǎn)，那么P(k,s)必定是從k到s的最短路徑。

證明：

假設(shè)P(i,j)={Vi…Vk…Vs…Vj}是從頂點(diǎn)i到j(luò)的最短路徑，則有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是從k到s的最短距離，那么必定存在另一條從k到s的最短路徑P(k,s)，那么P(i,j)=P(i,k)+P(k,s)+P(s,j)<P(i,j)。則與P(i,j)是從i到j(luò)的最短路徑相矛盾。因此該性質(zhì)得證。

因此，Dijkstra算法描述如下：

Dijikstra算法描述如下：

假設(shè)存在G=<V,E>，源頂點(diǎn)為V0，S={V0},distance[i]記錄V0到i的最短距離，matrix[i][j]記錄從i到j(luò)的邊的權(quán)值，即兩點(diǎn)之間的距離。

1）從V-S中選擇使dist[i]值最小的頂點(diǎn)i，將i加入到U中；

2）更新與i直接相鄰頂點(diǎn)的dist值。dist[j]=min{dist[j],dist[i]+matrix[i][j]}

3）直到S=V，所有頂點(diǎn)都包含進(jìn)來(lái)了，算法停止。

二、 具體操作步驟

根據(jù)其算法思想，確立操作步驟如下：

(1) 初始時(shí)，S只包含起點(diǎn)s；U包含除s外的其他頂點(diǎn)，且U中頂點(diǎn)的距離為"起點(diǎn)s到該頂點(diǎn)的距離"[例如，U中頂點(diǎn)v的距離為(s,v)的長(zhǎng)度，然后s和v不相鄰，則v的距離為∞]。

(2) 從U中選出"距離最短的頂點(diǎn)k"，并將頂點(diǎn)k加入到S中；同時(shí)，從U中移除頂點(diǎn)k。

(3) 更新U中各個(gè)頂點(diǎn)到起點(diǎn)s的距離。之所以更新U中頂點(diǎn)的距離，是由于上一步中確定了k是求出最短路徑的頂點(diǎn)，從而可以利用k來(lái)更新其它頂點(diǎn)的距離；例如，(s,v)的距離可能大于(s,k)+(k,v)的距離。

(4) 重復(fù)步驟(2)和(3)，直到遍歷完所有頂點(diǎn)。

三、代碼

def dijkstra(s, used, cost, distance, n):
  distance[s] = 0
  while True:
    # v在這里相當(dāng)于是一個(gè)哨兵，對(duì)包含起點(diǎn)s做統(tǒng)一處理！
    v = -1
    # 從未使用過(guò)的頂點(diǎn)中選擇一個(gè)距離最小的頂點(diǎn)
    for u in range(n):
      if not used[u] and (v == -1 or distance[u] < distance[v]):
        v = u
    if v == -1:
      # 說(shuō)明所有頂點(diǎn)都維護(hù)到S中了！
      break

    # 將選定的頂點(diǎn)加入到S中, 同時(shí)進(jìn)行距離更新
    used[v] = True
    # 更新U中各個(gè)頂點(diǎn)到起點(diǎn)s的距離。之所以更新U中頂點(diǎn)的距離，是由于上一步中確定了k是求出最短路徑的頂點(diǎn)，從而可以利用k來(lái)更新其它頂點(diǎn)的距離；例如，(s,v)的距離可能大于(s,k)+(k,v)的距離。
    for u in range(n):
      distance[u] = min(distance[u], distance[v] + cost[v][u])

  return distance


n, m, T = map(int, input().split())

# 標(biāo)記數(shù)組：used[v]值為False說(shuō)明改頂點(diǎn)還沒(méi)有訪問(wèn)過(guò)，在S中，否則在U中！
used = [False for _ in range(n)]
# 距離數(shù)組：distance[i]表示從源點(diǎn)s到ｉ的最短距離，distance[s]=0
distance = [float('inf') for _ in range(n)]
# cost[u][v]表示邊e=(u,v)的權(quán)值，不存在時(shí)設(shè)為INF
cost = [[float('inf') for _ in range(n)] for _ in range(n)]

for _ in range(m):
  e = list(map(int, input().split()))
  cost[e[0] - 1][e[1] - 1] = e[2]

dis1 = dijkstra(0, used[:], cost, distance[:], n)
d1 = dis1[-1]
dis2 = dijkstra(n-1, used[:], cost, distance[:], n)
d2 = dis2[0]

print((d1+d2)*T)

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論