計算機科學(xué)算法分析練習(xí)題

綜合試卷第=PAGE1*2-11頁（共=NUMPAGES1*22頁） 綜合試卷第=PAGE1*22頁（共=NUMPAGES1*22頁）PAGE①姓名所在地區(qū)姓名所在地區(qū)身份證號密封線1.請首先在試卷的標封處填寫您的姓名，身份證號和所在地區(qū)名稱。2.請仔細閱讀各種題目的回答要求，在規(guī)定的位置填寫您的答案。3.不要在試卷上亂涂亂畫，不要在標封區(qū)內(nèi)填寫無關(guān)內(nèi)容。一、選擇題1.算法的時間復(fù)雜度通常用哪個符號表示？

A.n

B.O(n)

C.log(n)

D.1/n

2.下面哪個不是排序算法？

A.冒泡排序

B.選擇排序

C.二分查找

D.快速排序

3.冒泡排序的平均時間復(fù)雜度是多少？

A.O(n)

B.O(n^2)

C.O(nlogn)

D.O(1)

4.快速排序的最好時間復(fù)雜度是多少？

A.O(n)

B.O(n^2)

C.O(nlogn)

D.O(n^2logn)

5.插入排序的最好時間復(fù)雜度是多少？

A.O(n)

B.O(n^2)

C.O(nlogn)

D.O(1)

6.歸并排序的空間復(fù)雜度是多少？

A.O(n)

B.O(n^2)

C.O(logn)

D.O(1)

7.堆排序的空間復(fù)雜度是多少？

A.O(n)

B.O(n^2)

C.O(logn)

D.O(1)

8.動態(tài)規(guī)劃算法通常用于解決哪種類型的問題？

A.線性規(guī)劃問題

B.矩陣計算問題

C.最優(yōu)化問題

D.圖論問題

9.下面哪個不是動態(tài)規(guī)劃的基本要素？

A.子問題分解

B.自頂向下的遞歸

C.最優(yōu)子結(jié)構(gòu)

D.子問題的重疊

10.動態(tài)規(guī)劃中的“重疊子問題”是指什么？

A.問題的子集

B.重復(fù)解決同樣子問題的情況

C.問題的解可以遞歸地定義

D.問題的解與輸入數(shù)據(jù)的大小成線性關(guān)系

答案及解題思路：

1.B.O(n)時間復(fù)雜度通常使用大O符號表示，O(n)表示線性時間復(fù)雜度。

2.C.二分查找二分查找是一種查找算法，而不是排序算法。

3.B.O(n^2)冒泡排序的平均時間復(fù)雜度是O(n^2)，因為它需要比較和交換每一對元素。

4.A.O(n)快速排序在最佳情況下具有O(n)的時間復(fù)雜度，這是在元素已排序的情況下發(fā)生的。

5.A.O(n)插入排序在最佳情況下，即輸入數(shù)組已經(jīng)排序的情況下，時間復(fù)雜度是O(n)。

6.A.O(n)歸并排序需要與待排序的元素數(shù)量相同的空間來存儲臨時數(shù)組。

7.C.O(logn)堆排序的空間復(fù)雜度主要取決于遞歸調(diào)用棧的深度，通常是O(logn)。

8.C.最優(yōu)化問題動態(tài)規(guī)劃算法通常用于解決最優(yōu)化問題，例如背包問題和最長公共子序列問題。

9.B.自頂向下的遞歸動態(tài)規(guī)劃不是基于自頂向下的遞歸，而是自底向上的遞歸或迭代。

10.B.重復(fù)解決同樣子問題的情況在動態(tài)規(guī)劃中，“重疊子問題”指的是子問題被多次計算的情況，這是動態(tài)規(guī)劃可以優(yōu)化的關(guān)鍵點。二、填空題1.算法的時間復(fù)雜度通常用______表示。

答案：大O符號（Onotation）

2.冒泡排序的基本操作是______。

答案：比較相鄰元素并交換它們的順序

3.快速排序的平均時間復(fù)雜度為______。

答案：O(nlogn)

4.歸并排序的空間復(fù)雜度為______。

答案：O(n)

5.動態(tài)規(guī)劃算法的核心思想是______。

答案：將復(fù)雜問題分解為簡單子問題，并存儲這些子問題的解以避免重復(fù)計算

6.動態(tài)規(guī)劃中的“最優(yōu)子結(jié)構(gòu)”是指______。

答案：問題的最優(yōu)解包含其子問題的最優(yōu)解

7.動態(tài)規(guī)劃中的“邊界條件”是指______。

答案：動態(tài)規(guī)劃問題中不需要進一步分解的最小問題或基本情況

8.動態(tài)規(guī)劃中的“狀態(tài)轉(zhuǎn)移方程”是指______。

答案：描述如何從子問題的解推導(dǎo)出原問題的解的方程

答案及解題思路：

1.答案：大O符號（Onotation）

解題思路：時間復(fù)雜度是描述算法運行時間的一個抽象度量，大O符號用來表示算法的時間復(fù)雜度，它給出了算法運行時間輸入規(guī)模增長的增長率。

2.答案：比較相鄰元素并交換它們的順序

解題思路：冒泡排序通過重復(fù)遍歷要排序的數(shù)列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。遍歷數(shù)列的工作是重復(fù)地進行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。

3.答案：O(nlogn)

解題思路：快速排序是一種分而治之的算法，它通過選取一個“基準”元素并將數(shù)組分為兩個子數(shù)組，一個包含小于基準的元素，另一個包含大于基準的元素。這個過程遞歸進行，直到每個子數(shù)組一個元素。平均情況下，快速排序的時間復(fù)雜度為O(nlogn)。

4.答案：O(n)

解題思路：歸并排序是一種分治法算法，它將數(shù)組分成兩半，遞歸地對它們進行排序，然后將排序好的數(shù)組合并。歸并排序需要與原數(shù)組同樣大小的輔助空間來合并排序后的數(shù)組，因此其空間復(fù)雜度為O(n)。

5.答案：將復(fù)雜問題分解為簡單子問題，并存儲這些子問題的解以避免重復(fù)計算

解題思路：動態(tài)規(guī)劃的核心思想是利用之前計算出的子問題的解來解決更復(fù)雜的問題，從而避免重復(fù)計算。通過將問題分解為更小的子問題，并存儲這些子問題的解，可以有效地減少計算量。

6.答案：問題的最優(yōu)解包含其子問題的最優(yōu)解

解題思路：最優(yōu)子結(jié)構(gòu)是指問題的最優(yōu)解包含了其子問題的最優(yōu)解。這意味著如果一個問題的最優(yōu)解可以通過其子問題的最優(yōu)解來構(gòu)造，那么它就具有最優(yōu)子結(jié)構(gòu)。

7.答案：動態(tài)規(guī)劃問題中不需要進一步分解的最小問題或基本情況

解題思路：邊界條件是動態(tài)規(guī)劃中的基本情況，它們是不需要進一步分解的最小問題。這些基本情況是遞歸的終止條件，通常對應(yīng)于問題的簡單或基本情況。

8.答案：描述如何從子問題的解推導(dǎo)出原問題的解的方程

解題思路：狀態(tài)轉(zhuǎn)移方程是動態(tài)規(guī)劃中的關(guān)鍵，它描述了如何根據(jù)子問題的解來計算原問題的解。通過狀態(tài)轉(zhuǎn)移方程，可以從已知的子問題解推導(dǎo)出更大的問題的解。三、判斷題1.算法的時間復(fù)雜度與輸入規(guī)模無關(guān)。（×）

解題思路：算法的時間復(fù)雜度通常與輸入規(guī)模有關(guān)，輸入規(guī)模越大，算法運行所需的時間通常會越長。

2.快速排序的平均時間復(fù)雜度為O(n^2)。（×）

解題思路：快速排序的平均時間復(fù)雜度是O(nlogn)，但在最壞情況下（即每次劃分都極度不平衡時），時間復(fù)雜度會退化到O(n^2)。

3.歸并排序是穩(wěn)定的排序算法。（√）

解題思路：歸并排序在合并過程中會保持相同元素的相對順序，因此是穩(wěn)定的排序算法。

4.動態(tài)規(guī)劃算法一定比貪心算法效率高。（×）

解題思路：動態(tài)規(guī)劃算法不一定比貪心算法效率高。貪心算法在某些問題上可能比動態(tài)規(guī)劃更高效。

5.動態(tài)規(guī)劃中的“重疊子問題”指的是子問題之間有重疊部分。（√）

解題思路：動態(tài)規(guī)劃中的“重疊子問題”是指子問題在算法的遞推過程中被重復(fù)求解的情況。

6.動態(tài)規(guī)劃中的“最優(yōu)子結(jié)構(gòu)”指的是子問題的最優(yōu)解可以組合成原問題的最優(yōu)解。（√）

解題思路：動態(tài)規(guī)劃中的“最優(yōu)子結(jié)構(gòu)”特性表明，原問題的最優(yōu)解可以通過其子問題的最優(yōu)解來構(gòu)建。

7.動態(tài)規(guī)劃中的“邊界條件”指的是算法的終止條件。（√）

解題思路：動態(tài)規(guī)劃中的“邊界條件”是指算法終止時需要滿足的條件，通常用于初始化或確定遞推關(guān)系的起點。

8.動態(tài)規(guī)劃中的“狀態(tài)轉(zhuǎn)移方程”指的是如何從子問題的解得到原問題的解。（√）

解題思路：動態(tài)規(guī)劃中的“狀態(tài)轉(zhuǎn)移方程”描述了如何根據(jù)子問題的解推導(dǎo)出原問題的解，是動態(tài)規(guī)劃算法的核心部分。四、簡答題1.簡述冒泡排序的基本思想。

冒泡排序是一種簡單的排序算法。它的工作原理是通過重復(fù)遍歷要排序的數(shù)列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。遍歷數(shù)列的工作是重復(fù)進行的，直到?jīng)]有再需要交換的元素為止，這意味著該數(shù)列已經(jīng)排序完成。

2.簡述快速排序的基本思想。

快速排序是一種高效的排序算法。它采用分而治之的策略，首先選擇一個“基準”元素，然后將數(shù)組分成兩部分：小于基準的元素和大于基準的元素。這樣，基準就處于其最終位置，然后遞歸地（分別對這兩部分）進行快速排序。

3.簡述歸并排序的基本思想。

歸并排序是一種分治策略的排序算法。它將數(shù)組分成兩半，遞歸地（分別）對它們進行排序，然后將排好序的兩半合并成一個完整的有序數(shù)組。這種算法保證了每次合并都是有序的，最終合并成一個完全有序的數(shù)組。

4.簡述動態(tài)規(guī)劃算法的基本思想。

動態(tài)規(guī)劃算法通過把原問題分解為相對簡單的子問題的方式求解復(fù)雜問題。它保存子問題的解，即通過重疊子問題的特性避免了解重復(fù)的計算。動態(tài)規(guī)劃通常用于優(yōu)化問題，它尋找問題的最優(yōu)解，并在求解過程中使用貪心策略。

5.簡述貪心算法的基本思想。

貪心算法通過在每一步選擇最優(yōu)的選擇來解決問題。這種方法并不保證總是能得到最優(yōu)解，但在很多情況下可以快速得到較好的解。貪心算法通常用于圖算法和某些最優(yōu)化問題。

6.簡述分治算法的基本思想。

分治算法是一種將復(fù)雜問題分解成小問題來解決的方法。它將原問題分解為幾個小問題，遞歸地解決這些小問題，然后將小問題的解合并，以得到原問題的解。分治算法通常具有遞歸性質(zhì)，它將問題分解成規(guī)模更小的相似問題。

7.簡述回溯算法的基本思想。

回溯算法通過摸索所有可能的解來解決問題。它從一個可能的解開始，如果當前解不滿足條件，則撤銷該解，回退到上一個狀態(tài)，嘗試另一個解。這個過程一直持續(xù)，直到找到滿足所有條件的解或確認當前路徑無法找到解。

8.簡述圖算法的基本思想。

圖算法是在圖結(jié)構(gòu)上操作的一系列算法。基本思想包括遍歷圖中的節(jié)點、尋找最短路徑、確定節(jié)點間的連通性、最小樹等問題。圖算法的關(guān)鍵是正確處理節(jié)點之間的邊和路徑。

答案及解題思路：

答案：

1.冒泡排序的基本思想是通過重復(fù)遍歷數(shù)列，交換相鄰的順序錯誤的元素，直到無序元素都被“冒泡”到數(shù)列的末尾。

2.快速排序的基本思想是通過選擇一個基準，將數(shù)組分為兩個子數(shù)組，一個包含小于基準的元素，另一個包含大于基準的元素，然后遞歸地對這兩個子數(shù)組進行排序。

3.歸并排序的基本思想是將數(shù)組分成兩半，分別排序，然后將排序后的子數(shù)組合并成一個完整的有序數(shù)組。

4.動態(tài)規(guī)劃算法的基本思想是將復(fù)雜問題分解為簡單子問題，通過保存子問題的解避免重復(fù)計算，并最終得到原問題的解。

5.貪心算法的基本思想是在每一步選擇當前看起來最優(yōu)的解，不保證全局最優(yōu)解，但往往能得到較好的局部最優(yōu)解。

6.分治算法的基本思想是將原問題分解為幾個小問題，遞歸地解決這些小問題，然后將解合并得到原問題的解。

7.回溯算法的基本思想是通過嘗試所有可能的解，回退到上一個狀態(tài)，如果當前路徑無效，則繼續(xù)摸索其他路徑。

8.圖算法的基本思想是在圖結(jié)構(gòu)上操作，解決遍歷、路徑、連通性、最小樹等問題。

解題思路：

對于每個算法的基本思想，理解其核心操作和流程是解題的關(guān)鍵。通過分析算法的具體步驟和實現(xiàn)細節(jié)，可以更好地掌握其工作原理和應(yīng)用場景。五、分析題1.分析冒泡排序、快速排序、歸并排序、堆排序的時間復(fù)雜度和空間復(fù)雜度。

冒泡排序：

時間復(fù)雜度：最壞情況下O(n^2)，平均情況下O(n^2)，最好情況下O(n)。

空間復(fù)雜度：O(1)，因為它是原地排序算法。

快速排序：

時間復(fù)雜度：最壞情況下O(n^2)，平均情況下O(nlogn)。

空間復(fù)雜度：O(logn)，因為遞歸調(diào)用棧的深度。

歸并排序：

時間復(fù)雜度：O(nlogn)，無論最好、平均還是最壞情況。

空間復(fù)雜度：O(n)，因為需要額外的空間來合并子數(shù)組。

堆排序：

時間復(fù)雜度：O(nlogn)，無論最好、平均還是最壞情況。

空間復(fù)雜度：O(1)，因為它是原地排序算法。

2.分析動態(tài)規(guī)劃算法在解決最短路徑問題中的應(yīng)用。

動態(tài)規(guī)劃算法在解決最短路徑問題中的應(yīng)用，如Dijkstra算法和FloydWarshall算法：

Dijkstra算法適用于圖中的邊權(quán)值非負的情況，時間復(fù)雜度為O((VE)logV)。

FloydWarshall算法適用于所有邊權(quán)值可能為負的情況，時間復(fù)雜度為O(V^3)。

3.分析貪心算法在解決背包問題中的應(yīng)用。

貪心算法在解決背包問題中的應(yīng)用，如0/1背包問題：

貪心算法通過每次選擇價值最大的物品來填充背包，直到背包容量滿或沒有更多物品可選。

時間復(fù)雜度通常為O(nW)，其中n是物品數(shù)量，W是背包容量。

4.分析分治算法在解決排序問題中的應(yīng)用。

分治算法在解決排序問題中的應(yīng)用，如快速排序：

快速排序通過將數(shù)組分成兩個子數(shù)組，分別對它們進行排序，然后合并結(jié)果。

時間復(fù)雜度平均為O(nlogn)，最壞情況下為O(n^2)。

5.分析回溯算法在解決組合問題中的應(yīng)用。

回溯算法在解決組合問題中的應(yīng)用，如八皇后問題：

回溯算法通過遞歸嘗試所有可能的組合，并在不滿足條件時回溯到上一個狀態(tài)。

時間復(fù)雜度取決于問題的具體組合數(shù)量，通常是指數(shù)級的。

6.分析圖算法在解決最短路徑問題中的應(yīng)用。

圖算法在解決最短路徑問題中的應(yīng)用，如Dijkstra算法和BellmanFord算法：

Dijkstra算法適用于圖中的邊權(quán)值非負的情況，時間復(fù)雜度為O((VE)logV)。

BellmanFord算法適用于所有邊權(quán)值可能為負的情況，時間復(fù)雜度為O(VE)。

7.分析圖算法在解決最小樹問題中的應(yīng)用。

圖算法在解決最小樹問題中的應(yīng)用，如Prim算法和Kruskal算法：

Prim算法通過逐步添加邊來構(gòu)建最小樹，時間復(fù)雜度為O(ElogV)。

Kruskal算法通過排序所有邊并按順序選擇最小邊來構(gòu)建最小樹，時間復(fù)雜度為O(ElogE)。

8.分析圖算法在解決最短路徑問題中的應(yīng)用。

（此部分與第6點內(nèi)容重復(fù)，故不再重復(fù)描述。）

答案及解題思路：

答案：

1.冒泡排序：時間復(fù)雜度O(n^2)，空間復(fù)雜度O(1)；快速排序：時間復(fù)雜度O(nlogn)，空間復(fù)雜度O(logn)；歸并排序：時間復(fù)雜度O(nlogn)，空間復(fù)雜度O(n)；堆排序：時間復(fù)雜度O(nlogn)，空間復(fù)雜度O(1)。

2.Dijkstra算法：時間復(fù)雜度O((VE)logV)；FloydWarshall算法：時間復(fù)雜度O(V^3)。

3.0/1背包問題：時間復(fù)雜度O(nW)。

4.快速排序：平均時間復(fù)雜度O(nlogn)，最壞情況時間復(fù)雜度O(n^2)。

5.八皇后問題：時間復(fù)雜度指數(shù)級。

6.Dijkstra算法：時間復(fù)雜度O((VE)logV)；BellmanFord算法：時間復(fù)雜度O(VE)。

7.Prim算法：時間復(fù)雜度O(ElogV)；Kruskal算法：時間復(fù)雜度O(ElogE)。

解題思路：

1.分析每種排序算法的執(zhí)行過程，確定其時間復(fù)雜度和空間復(fù)雜度。

2.針對最短路徑問題，了解不同算法的適用場景和計算復(fù)雜度。

3.對于背包問題，應(yīng)用貪心策略選擇物品，并分析其時間復(fù)雜度。

4.分析分治算法在排序問題中的應(yīng)用，包括其遞歸過程和復(fù)雜度分析。

5.回溯算法通過遞歸嘗試所有可能的組合，并回溯以找到解。

6.圖算法在解決最短路徑問題時，需要根據(jù)圖的性質(zhì)選擇合適的算法。

7.最小樹問題中，根據(jù)圖的邊權(quán)值選擇合適的圖算法。

8.對于重復(fù)問題，直接引用之前分析的內(nèi)容。六、編程題1.實現(xiàn)冒泡排序算法

編寫一個函數(shù)，該函數(shù)接收一個整數(shù)數(shù)組作為輸入，并返回一個排序后的數(shù)組。

使用冒泡排序算法實現(xiàn)排序，要求輸出排序的過程。

2.實現(xiàn)快速排序算法

編寫一個函數(shù)，該函數(shù)接收一個整數(shù)數(shù)組作為輸入，并返回一個排序后的數(shù)組。

使用快速排序算法實現(xiàn)排序，要求輸出排序的過程。

3.實現(xiàn)歸并排序算法

編寫一個函數(shù)，該函數(shù)接收一個整數(shù)數(shù)組作為輸入，并返回一個排序后的數(shù)組。

使用歸并排序算法實現(xiàn)排序，要求輸出排序的過程。

4.實現(xiàn)動態(tài)規(guī)劃算法解決斐波那契數(shù)列問題

編寫一個函數(shù)，該函數(shù)接收一個整數(shù)`n`作為輸入，并返回斐波那契數(shù)列的第`n`項。

使用動態(tài)規(guī)劃算法實現(xiàn)，并分析算法的時間復(fù)雜度和空間復(fù)雜度。

5.實現(xiàn)貪心算法解決背包問題

編寫一個函數(shù)，該函數(shù)接收一個物品數(shù)組`items`和背包容量`capacity`作為輸入，返回能夠裝入背包的物品的最大價值。

使用貪心算法實現(xiàn)，并分析算法的正確性和效率。

6.實現(xiàn)分治算法解決排序問題

編寫一個函數(shù)，該函數(shù)接收一個整數(shù)數(shù)組作為輸入，并返回一個排序后的數(shù)組。

使用分治算法中的排序算法（如快速排序）實現(xiàn)排序，要求輸出排序的過程。

7.實現(xiàn)回溯算法解決組合問題

編寫一個函數(shù)，該函數(shù)接收一個整數(shù)`n`和一個目標值`target`作為輸入，返回所有可能的組合。

使用回溯算法實現(xiàn)，要求輸出所有可能的組合。

8.實現(xiàn)圖算法解決最短路徑問題

編寫一個函數(shù)，該函數(shù)接收一個圖的鄰接矩陣作為輸入，并返回兩個頂點之間的最短路徑。

使用圖算法中的Dijkstra算法或FloydWarshall算法實現(xiàn)，并分析算法的正確性和效率。

答案及解題思路：

1.冒泡排序算法

答案：

defbubble_sort(arr):

n=len(arr)

foriinrange(n):

forjinrange(0,ni1):

ifarr[j]>arr[j1]:

arr[j],arr[j1]=arr[j1],arr[j]

returnarr

解題思路：通過兩重循環(huán)，每次循環(huán)都將相鄰的兩個元素進行比較，如果順序錯誤就交換它們的位置，直到整個數(shù)組排序完成。

2.快速排序算法

答案：

defquick_sort(arr):

iflen(arr)=1:

returnarr

pivot=arr[len(arr)//2]

left=[xforxinarrifxpivot]

middle=[xforxinarrifx==pivot]

right=[xforxinarrifx>pivot]

returnquick_sort(left)middlequick_sort(right)

解題思路：選擇一個基準值（pivot），將數(shù)組分成小于基準值、等于基準值和大于基準值的三個子數(shù)組，然后遞歸地對小于和大于基準值的子數(shù)組進行快速排序。

3.歸并排序算法

答案：

defmerge_sort(arr):

iflen(arr)=1:

returnarr

mid=len(arr)//2

left=merge_sort(arr[:mid])

right=merge_sort(arr[mid:])

returnmerge(left,right)

defmerge(left,right):

result=

i=j=0

whileilen(left)andjlen(right):

ifleft[i]right[j]:

result.append(left[i])

i=1

else:

result.append(right[j])

j=1

result.extend(left[i:])

result.extend(right[j:])

returnresult

解題思路：將數(shù)組分成兩半，遞歸地對兩半進行歸并排序，然后將排序后的兩半合并。

4.動態(tài)規(guī)劃解決斐波那契數(shù)列問題

答案：

deffibonacci(n):

ifn=1:

returnn

memo=[0,1]

foriinrange(2,n1):

memo.append(memo[1]memo[2])

returnmemo[n]

解題思路：使用一個數(shù)組存儲斐波那契數(shù)列的值，通過迭代計算每個數(shù)，避免重復(fù)計算。

5.貪心算法解決背包問題

答案：

defknapsack(items,capacity):

items.sort(key=lambdax:x[1]/x[0],reverse=True)

total_value=0

foriteminitems:

ifitem[0]=capacity:

capacity=item[0]

total_value=item[1]

else:

break

returntotal_value

解題思路：根據(jù)物品的價值密度（價值/重量）對物品進行排序，選擇價值密度最大的物品加入背包，直到背包容量不足。

6.分治算法解決排序問題

答案（使用快速排序）：

快速排序的函數(shù)已在上述第2點給出

解題思路：參考第2點快速排序的解題思路。

7.回溯算法解決組合問題

答案：

defbine(n,target):

defbacktrack(start,target):

iftarget==0:

result.append(path)

return

foriinrange(start,n1):

path.append(i)

backtrack(i1,targeti)

path.pop()

result=

path=

backtrack(1,target)

returnresult

解題思路：遞歸地選擇一個數(shù)字，如果該數(shù)字不滿足條件則回溯，否則繼續(xù)選擇下一個數(shù)字。

8.圖算法解決最短路徑問題

答案（使用Dijkstra算法）：

defdijkstra(graph,start):

distances={vertex:float('infinity')forvertexingraph}

distances[start]=0

visited=set()

whilevisited!=set(graph):

min_distance=float('infinity')

forvertexingraph:

ifvertexnotinvisitedanddistances[vertex]min_distance:

min_distance=distances[vertex]

current_vertex=vertex

visited.add(current_vertex)

forneighbor,weightingraph[current_vertex].items():

distances[neighbor]=min(distances[neighbor],distances[current_vertex]weight)

returndistances

解題思路：初始化所有頂