อัลกอริทึมของ Dijsktra: C++, Python ตัวอย่างรหัส
ซาราห์ เฉิน
เส้นทางที่สั้นที่สุดหรือระยะทางที่สั้นที่สุดคืออะไร?
เส้นทางจากจุดยอดต้นทางไปยังจุดยอดปลายทางที่มีต้นทุนน้อยที่สุดคือเส้นทางที่สั้นที่สุดหรือระยะทางที่สั้นที่สุด ในทฤษฎีกราฟ มีความเป็นไปได้ที่จะมีหลายเส้นทางจากต้นทางไปยังปลายทาง ระหว่างเส้นทางเหล่านี้ หากมีเส้นทางที่มีค่าใช้จ่ายขั้นต่ำ เราสามารถเรียกมันว่าอัลกอริธึมเส้นทางที่สั้นที่สุดได้
ที่นี่ "ต้นทุน" หมายถึงจำนวนโหนดในเส้นทางหรือผลรวมของต้นทุนในแต่ละเส้นทาง เส้นทางอาจมีขอบหนึ่งหรือหลายขอบก็ได้ การเชื่อมต่อระหว่างจุดยอดสองจุดเรียกว่า "ขอบ" มีอัลกอริทึมเส้นทางที่สั้นที่สุดหลายประเภท เช่น อัลกอริทึมของ Dijkstra อัลกอริทึมของ Bellman-Ford เป็นต้น
ที่นี่เราจะหารือเกี่ยวกับอัลกอริทึมของ Dijkstra
มาดูกราฟถ่วงน้ำหนักต่อไปนี้:
- คำว่า "ถ่วงน้ำหนัก" หมายถึงการย้ายต้นทุนจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง ตัวอย่างเช่น การย้ายจากโหนด 1 ไปยังโหนด 2 ต้นทุนหรือน้ำหนักคือ 1
- เส้นทางระหว่างโหนด 1 ถึงโหนด 2 เรียกว่าส่วนขอบ
- “Undirected” หมายความว่าคุณสามารถย้ายโหนดหนึ่งไปยังอีกโหนดหนึ่งและกลับไปยังโหนดก่อนหน้าได้ ดังนั้น หากเราพยายามค้นหาเส้นทางทั้งหมดจากโหนด 1 ถึงโหนด 7 มันจะเป็น:
| เส้นทางหรือเส้นทาง | ราคา |
|---|---|
| 1-2-6-7 | (1+3+3) = 7 |
| 1-2-3-7 | (1+9+1) = 11 |
| 1-3-7 | (7+1) = 8 |
| 1-4-5-7 | (6+2+5) = 13 |
ในสี่เส้นทางนี้เราจะเห็นว่าเส้นทางแรกมีค่าใช้จ่าย 7 เส้นทาง จึงเป็นเส้นทางที่สั้นที่สุดในแง่ของต้นทุน
อัลกอริทึมของ Dijkstra ทำงานอย่างไร
อัลกอริธึม Dijkstra สามารถค้นหาระยะทางที่สั้นที่สุดในกราฟถ่วงน้ำหนักทั้งแบบตรงและไม่ตรงทิศทาง อัลกอริทึมนี้โลภมากเพราะมักจะเลือกโหนดที่สั้นที่สุดหรือใกล้เคียงที่สุดจากจุดเริ่มต้นเสมอ คำว่า "โลภ" หมายความว่าในบรรดาผลลัพธ์หรือผลลัพธ์ชุดหนึ่ง อัลกอริธึมจะเลือกสิ่งที่ดีที่สุด
ที่นี่ เรากำลังพยายามหาเส้นทางที่สั้นที่สุดในบรรดาเส้นทางอื่นๆ ทั้งหมด ดังนั้น อัลกอริทึมของ Dijkstra จะค้นหาเส้นทางที่สั้นที่สุดทั้งหมดจากโหนดปลายทางเดียว เป็นผลให้มีพฤติกรรมเหมือนก อัลกอริทึมโลภ.
ในส่วน "ตัวอย่าง" ด้านล่าง คุณจะเห็นวิธีการทีละขั้นตอน มันทำงานดังนี้:
ขั้นตอน 1) เริ่มต้นโหนดเริ่มต้นด้วยต้นทุน 0 และส่วนที่เหลือของโหนดเป็นต้นทุนอินฟินิตี้
ขั้นตอน 2) รักษาอาร์เรย์หรือรายการเพื่อติดตามโหนดที่เยี่ยมชม
ขั้นตอน 3) อัปเดตต้นทุนโหนดด้วยต้นทุนขั้นต่ำ สามารถทำได้โดยการเปรียบเทียบต้นทุนปัจจุบันกับต้นทุนเส้นทาง (การสาธิตแสดงอยู่ในส่วนตัวอย่าง)
ขั้นตอน 4) ทำขั้นตอนที่ 3 ต่อไปจนกว่าจะมีการเยี่ยมชมโหนดทั้งหมด
หลังจากทำตามขั้นตอนทั้งหมดนี้แล้ว เราจะพบเส้นทางที่มีต้นทุนขั้นต่ำจากต้นทางไปยังปลายทาง
ความแตกต่างระหว่าง Dijkstra และ BFS, DFS
ความแตกต่างหลักระหว่าง Dijkstra และ BFS-DFS คือ Dijkstra เป็นอัลกอริทึมการค้นหาเส้นทางที่สั้นที่สุด ส่วน BFS และ DFS เป็นอัลกอริทึมการค้นหาเส้นทาง โดยทั่วไปแล้ว BFS และ DFS จะไม่คำนึงถึงต้นทุนในการค้นหาเส้นทาง ดังนั้นอัลกอริทึมเหล่านี้จึงไม่สามารถรับประกันเส้นทางที่สั้นที่สุดได้
ตาราง 2 มิติสาธิตวิธีการทำงานของ BFS
การสาธิตนี้บ่งชี้ว่า BFS พบเฉพาะเส้นทางเท่านั้น อย่างไรก็ตาม ไม่สนใจน้ำหนักของเส้นทาง บีเอฟเอส (การค้นหาแบบกว้าง - แรก) ถือว่าการเดินทางจากโหนดหนึ่งไปยังอีกโหนดหนึ่งจะมีราคาเพียง 1
แต่ให้เราดูกราฟตัวอย่าง:
ที่นี่จะค้นหาเส้นทางในระดับ 2 BFS ลัดเลาะไปตามกราฟตามลำดับระดับ ดังนั้นจึงเดินทางดังนี้:
ขั้นตอน 1) เริ่มจากโหนด “1” และเยี่ยมชมโหนดที่อยู่ติดกันทั้งหมด 2,3,4
ขั้นตอน 2) ทำเครื่องหมายโหนด 2,3,4 เป็นระดับ 1 และเยี่ยมชมโหนดที่อยู่ติดกัน มันจะสำรวจโหนดที่อยู่ติดกันทั้งหมดต่อไปจนกว่าจะถึงโหนดปลายทาง
ในแง่ของ DFS มันจะเคลื่อนผ่านเส้นทางจาก 1 ถึง 7 ดังต่อไปนี้:
- 1→2→3→7 (ราคาเดิม 10, DFS ราคา 3)
- 1→2→6→7 (ราคาเดิม 7, DFS ราคา 3)
- 1→3→7 (ราคาเดิม 8, DFS ราคา 2)
- 1→4→5→7 (ราคาเดิม 13, DFS ราคา 3)
ดังที่เราเห็น DFS จะคำนวณต้นทุนเส้นทางด้วยจำนวนความลึกหรือจำนวนขอบ
DFS ดำเนินการดังต่อไปนี้:
- DFS สามารถค้นหาเส้นทางจากต้นทาง (เริ่มต้นจุดยอด) ไปยังปลายทาง
- ไม่สามารถรับประกันได้ว่าเส้นทางที่ค้นพบจากโหนดต้นทางไปยังปลายทางนั้นเป็นเส้นทางที่สั้นที่สุดหรือไม่
อย่างไรก็ตาม ในแง่ของอัลกอริทึม Dijkstra มันจะเลือกขอบตามต้นทุน เนื่องจากเป็นอัลกอริธึมที่ละโมบ มันจะเลือกเส้นทางต้นทุนที่ดีที่สุดหรือต่ำสุด
ตัวอย่างอัลกอริทึมของ Dijkstra
อัลกอริทึมของ Dijkstra ใช้ต้นทุนหรือน้ำหนักในการคำนวณต้นทุนรวมของเส้นทาง
เป้าหมายของอัลกอริทึมของ Dijkstra คือการลดต้นทุนหรือน้ำหนักทั้งหมดให้เหลือน้อยที่สุด ในตัวอย่างที่แสดงข้างต้น เราจะค้นหาเส้นทางที่ดีที่สุดจากโหนด 1 ไปยังโหนด 7 จากนั้นจึงคำนวณต้นทุนทั้งหมด
ในอัลกอริทึมของ Dijkstra มันจะค้นหาเส้นทางที่สั้นที่สุดโดยการคำนวณน้ำหนัก จะไม่ค้นหาเส้นทางที่เป็นไปได้ทั้งหมด ให้เราสาธิตอัลกอริทึมของ Dijkstra ด้วยตัวอย่าง ตัวอย่างเช่น คุณถูกขอให้ค้นหาเส้นทางที่สั้นที่สุดจากโหนด 1 ถึง 7
สำหรับกระบวนการนี้ มีขั้นตอนดังต่อไปนี้:
ขั้นตอน 1) เริ่มต้นต้นทุนโหนดเริ่มต้นเป็น 0
โหนดที่เหลือ กำหนด “อินฟ”. หมายความว่าไม่มีเส้นทางอยู่ระหว่างจุดยอดเริ่มต้น (แหล่งที่มา) และโหนด หรือเส้นทางที่ยังไม่ได้เยี่ยมชม
ขั้นตอน 2) เมื่อคุณเลือกโหนด 1 โหนดนั้นจะถูกทำเครื่องหมายว่าเยี่ยมชมแล้ว จากนั้นอัปเดตเพื่อนบ้านที่อยู่ติดกันทั้งหมดของโหนด 1 2,3,4 เป็นโหนดใกล้เคียงของโหนด 1
ขณะอัปเดตต้นทุน เราต้องปฏิบัติตามขั้นตอนด้านล่าง:
เราสามารถอัปเดตต้นทุนของแต่ละโหนดได้โดยใช้สูตรด้านบน ตัวอย่างเช่น เราอยู่ที่โหนด 1 และเราจำเป็นต้องอัปเดตต้นทุนของโหนดที่อยู่ติดกัน 2,3,4
หลังจากอัพเดตแล้ว ราคาหรือน้ำหนักจะเป็นดังนี้:
ขั้นตอนที่ 3) สำหรับโหนด “2” เพื่อนบ้านคือ 6 และ 3 เรากำลังอัปเดตต้นทุนที่ "6" โดยการเปรียบเทียบค่าอนันต์ (มูลค่าปัจจุบัน) ต้นทุนของโหนด 2 + ต้นทุนเส้นทางจาก 2 ถึง 6 พูดง่ายๆ ว่าโหนด “6” จะมีราคา 1+3 หรือ 4
โหนด 3 เป็นเพื่อนบ้านของโหนด 2 อย่างไรก็ตาม เราคำนวณต้นทุนในขั้นตอนก่อนหน้า ซึ่งก็คือ 7 ตอนนี้ หากเส้นทางของเราคือ 1-2-3 โหนด 3 จะมีราคา 10 เส้นทาง 1-2- 3 จะมีราคา 10 ในขณะที่ 1 ถึง 3 จะมีราคา 7
ขั้นตอนที่ 4) สำหรับโหนด 3 โหนดข้างเคียงคือ 7 ดังนั้น เมื่อเปรียบเทียบค่าปัจจุบันของโหนด 7 กับต้นทุนเส้นทาง (7+1) หรือ 8 เราจะอัปเดตต้นทุนของโหนด 7 นั่นคือ 8
ดังนั้นเราจึงค้นหาเส้นทางจากโหนด 1 ไปยังโหนด 7 และมันคือ 1 → 3 → 7 ราคาคือ 8
ขั้นตอนที่ 5) สำหรับโหนด 4 เราจะอัปเดตต้นทุนโหนดที่อยู่ติดกันตามลำดับ ดังนั้น โหนด “5” จะมีราคาที่อัปเดตเป็น 8 หลังจากขั้นตอนที่ 4,5 จะมีลักษณะดังนี้:
ตอนนี้เส้นทาง 1-3-7 มีราคา 8 (ก่อนหน้านี้) โหนด “7” ไม่ได้ถูกทำเครื่องหมายว่าเข้าชมแล้ว เนื่องจากเราสามารถเข้าถึงโหนด “7” จากโหนด “6” เส้นทาง “1-2-6” มีราคา 4 ดังนั้นเส้นทาง 1-2-6-7 จะมีราคา 7
เนื่องจาก 7 < 8 นั่นคือสาเหตุที่เส้นทางที่สั้นที่สุดจากจุดยอดต้นทาง “1” ไปยังจุดยอดปลายทาง “7” จะเป็น 1-2-6-7 และราคาคือ 7 ก่อนหน้านี้คือ 1-3-7 และราคา อายุ 8 ขวบ
ดังนั้นกราฟสุดท้ายจะเป็นดังนี้:
ขอบที่มีเส้นสีดำเป็นเส้นทางที่สั้นที่สุดของเราตั้งแต่ 1 ถึง 7 และมีค่าใช้จ่าย 7
อัลกอริทึมของรหัสหลอก Dijkstra
นี่คือรหัสหลอกสำหรับอัลกอริทึมของ Dijkstra
Dijkstra(G, S):
for each vertex V in G
distance[V] & lt; - Infinity
previous[V] & lt; - NULL
if V does not equal S, then,
(priority queue) Q.push(V)
distance[S] = 0
While Q is not empty
U & lt; - Extract the MIN from Q
For each unvisited adjacent V of U
TotalDistance & lt; - distance[U] + edge_cost(U, V)
if TotalDistance is less than distance[V], then
distance[V] & lt; - TotalDistance
previous[V] & lt; - u
return distance, previous
C++ อัลกอริทึมของ Dijkstra
เพื่อนำอัลกอริทึมของ Dijkstra ไปใช้โดยใช้ C++นี่คือรหัส:
#include <bits/stdc++.h>
using namespace std;
#define size 7
int minimumDistance(int distance[], bool visited[]) {
int min = INT_MAX;
int min_index = INT_MAX;
for (int i = 0; i < size; i++) {
if (!visited[i] & amp; & distance[i] <= min) {
min = distance[i];
min_index = i;
}
}
return min_index;
}
void printParentPath(int parent[], int i) {
if (parent[i] == -1) {
return;
}
printParentPath(parent, parent[i]);
cout << i + 1 << " ";
}
void dijkstra(int graph[size][size], int source) {
int distance[size];
bool visited[size];
int parent[size];
for (int i = 0; i < size; i++) {
parent[0] = -1;
distance[i] = INT_MAX;
visited[i] = false;
}
distance[source] = 0;
for (int i = 0; i < size - 1; i++) {
int U = minimumDistance(distance, visited);
visited[U] = true;
for (int j = 0; j < size; j++) {
int curr_distance = distance[U] + graph[U][j];
if (!visited[j] & amp; & graph[U][j] & amp; &
curr_distance < distance[j]) {
parent[j] = U;
distance[j] = curr_distance;
}
}
}
cout << "Vertex\t\tDistance\tPath" << endl;
for (int i = 1; i < size; i++) {
cout << source + 1 << "->" << i + 1 << "\t\t" << distance[i] << "\t\t"
<< source + 1 << " ";
printParentPath(parent, i);
cout << endl;
}
}
int main() {
int graph[size][size] = {{0, 1, 7, 6, 0, 0, 0}, {1, 0, 9, 0, 0, 3, 0},
{7, 9, 0, 0, 0, 0, 1}, {6, 0, 0, 0, 2, 0, 0},
{0, 0, 0, 2, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 3},
{0, 0, 0, 0, 5, 3, 0}};
dijkstra(graph, 0);
}
Output:
Vertex Distance Path 1->2 1 1 2 1->3 7 1 3 1->4 6 1 4 1->5 8 1 4 5 1->6 4 1 2 6 1->7 7 1 2 6 7
Python อัลกอริทึมของ Dijkstra
เพื่อนำอัลกอริทึมของ Dijkstra ไปใช้โดยใช้ หลามนี่คือรหัส:
num_of_vertex = 7
def minimumDistance(distance, visited):
_min = 1e11
min_index = 1e11
for i in range(num_of_vertex):
if not visited[i] and distance[i] & lt; = _min:
_min = distance[i]
min_index = i
return min_index
def printParentNode(parent, i):
if parent[i] == -1:
return
printParentNode(parent, parent[i])
print("{} ".format(i + 1), end = "")
def dijkstra(graph, src):
distance = list()
visited = list()
parent = list()
for i in range(num_of_vertex):
parent.append(-1)
distance.append(1e11)
visited.append(False)
distance[src] = 0
for i in range(num_of_vertex - 1):
U = minimumDistance(distance, visited)
visited[U] = True
for j in range(num_of_vertex):
curr_distance = distance[U] + graph[U][j]
if not visited[j] and graph[U][j] and curr_distance & lt;
distance[j]: parent[j] = U
distance[j] = curr_distance
print("Vertex\t\tDistance\tPath")
for i in range(num_of_vertex):
print("{}->{}\t\t{}\t\t{}
".format(src + 1, i + 1, distance[i], src + 1), end = "")
printParentNode(parent, i)
print("")
graph = [
[0, 1, 7, 6, 0, 0, 0],
[1, 0, 9, 0, 0, 3, 0],
[7, 9, 0, 0, 0, 0, 1],
[6, 0, 0, 0, 2, 0, 0],
[0, 0, 0, 2, 0, 0, 0],
[0, 3, 0, 0, 0, 0, 3],
[0, 0, 0, 0, 5, 3, 0]
]
dijkstra(graph, 0)
Output:
Vertex Distance Path 1->1 0 1 1->2 1 1 2 1->3 7 1 3 1->4 6 1 4 1->5 8 1 4 5 1->6 4 1 2 6 1->7 7 1 2 6 7
เราจะเห็นว่าอัลกอริทึมคำนวณระยะทางที่สั้นที่สุดจากโหนดต้นทาง
การประยุกต์ใช้อัลกอริทึม Dijkstra
Dijkstra Algo มีชุดการใช้งานมากมาย ในบรรดาสิ่งเหล่านี้มีการใช้กันอย่างแพร่หลายในด้านเครือข่าย นี่คือการใช้งานอัลกอริทึมของ Dijkstra ในชีวิตจริง:
Dijkstra ในแผนที่ Google: โดยพื้นฐานแล้ว อัลกอริธึมนี้เป็นแกนหลักในการค้นหาเส้นทางที่สั้นที่สุด ดังที่เราเห็นได้จากเอาต์พุตข้อมูลโค้ดด้านบน
Google ไม่ได้ใช้อัลกอริทึม Dijkstra แบบธรรมดา แต่จะใช้เวอร์ชันที่แก้ไขแทน เมื่อคุณเลือกจุดหมายปลายทาง ระบบจะแสดงเส้นทางหลายเส้นทางใน Google Map ในบรรดาเส้นทางเหล่านี้ บางเส้นทางจะถูกจัดเรียงสำหรับผู้ใช้ เส้นทางที่เลือกเหล่านี้ขึ้นอยู่กับ "เวลา" ดังนั้น “เวลา” จึงเป็นต้นทุนส่วนได้เปรียบสำหรับเส้นทางที่สั้นที่สุด
Dijkstra ในการกำหนดเส้นทาง IP: การกำหนดเส้นทางไอพี เป็นศัพท์เฉพาะทางเครือข่าย หมายความว่าแพ็กเก็ตข้อมูลของคุณถูกส่งไปยังผู้รับผ่านเส้นทางที่แตกต่างกันอย่างไร เส้นทางเหล่านี้ประกอบด้วยเราเตอร์ เซิร์ฟเวอร์ ฯลฯ ในการกำหนดเส้นทาง IP มีโปรโตคอลหลายประเภท
โปรโตคอลเหล่านี้ช่วยให้เราเตอร์ค้นหาเส้นทางที่สั้นที่สุดในการส่งข้อมูล ชื่อโปรโตคอลหนึ่งคือ “OSPF (Open Shortest Path First)” OSPF ใช้อัลกอริทึม Dijkstra เราเตอร์จะรักษาตารางเส้นทาง เราเตอร์แต่ละตัวจะแชร์ตารางของตัวเองกับเราเตอร์ข้างเคียง หลังจากได้รับตารางที่อัปเดตแล้ว เราเตอร์จะต้องคำนวณเส้นทางทั้งหมดอีกครั้ง เมื่อถึงเวลานั้น เราเตอร์จะใช้อัลกอริทึม Dijkstra
ข้อจำกัดของอัลกอริทึมของ Dijkstra
อัลกอริธึม Dijkstra ไม่สามารถรับประกันเส้นทางที่สั้นที่สุดในกราฟขอบลบ อัลกอริทึม Dijkstra เป็นไปตามวิธีการเหล่านี้:
- เส้นทางที่สั้นที่สุดเส้นหนึ่งจะถูกนำมาจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง
- เมื่อเลือกเส้นทางที่สั้นที่สุดระหว่างสองโหนดแล้ว จะไม่ถูกคำนวณอีก
ต่อไปนี้ ให้สังเกตสองตัวอย่างที่มีขอบเป็นลบ
ในกราฟด้านซ้าย มีจุดยอดสามจุด Dijkstra จะทำงานบนกราฟดังต่อไปนี้:
ขั้นตอน 1) การเริ่มต้นจุดยอด “1” จะถูกเตรียมใช้งานให้เป็นศูนย์ โหนดอื่นๆ จะมีค่าอนันต์
ขั้นตอน 2) ทำเครื่องหมายโหนด “1” ว่าเยี่ยมชมแล้วและรวมไว้ในเส้นทางที่สั้นที่สุด
ขั้นตอน 3) ระยะห่างของโหนดต้นทาง 1 ถึงโหนด "2" และ "3" ถูกตั้งค่าเป็นอนันต์ เนื่องจากยังไม่ได้คำนวณเส้นทางที่สั้นที่สุด ดังนั้นเส้นทางใด ๆ ที่มีราคาน้อยกว่าอนันต์จะถูกเพิ่มเข้าไปในเส้นทางที่สั้นที่สุด (แนวทางโลภ)
ขั้นตอน 4) การอัปเดตระยะห่างจากจุดยอดต้นทางหรือโหนดต้นทาง "1" ถึง "2" น้ำหนักปัจจุบันจะเป็น 5 (5
ขั้นตอน 5) ตอนนี้ถ้าเราตรวจสอบระยะทางที่สั้นที่สุดจากโหนด “1” เราจะพบว่า 5 เป็นระยะทางที่สั้นที่สุดสำหรับขอบ 1–> 2 ดังนั้น โหนด “2” จะถูกทำเครื่องหมายว่าเยี่ยมชมแล้ว
ในทำนองเดียวกัน โหนด “3” จะถูกทำเครื่องหมายว่าเยี่ยมชมแล้ว เนื่องจากระยะทางที่สั้นที่สุดคือ 3
อย่างไรก็ตาม หากเราสังเกต มีเส้นทาง 1-3-2 ที่จะมีราคาเพียง 2 เท่านั้น แต่ Dijkstra แสดงให้เห็นว่าจากโหนด “1” ถึงโหนด “2” ระยะทางที่สั้นที่สุดคือ 5 ดังนั้น Dijkstra จึงล้มเหลวในการคำนวณระยะทางที่สั้นที่สุด เว้นระยะห่างอย่างถูกต้อง สาเหตุที่มันเกิดขึ้นก็คือ Dijkstra เป็นอัลกอริธึมที่โลภ ดังนั้น เมื่อทำเครื่องหมายว่าเยี่ยมชมโหนดแล้ว โหนดนั้นจะไม่ได้รับการพิจารณาใหม่ แม้ว่าอาจมีเส้นทางที่สั้นกว่าก็ตาม ปัญหานี้เกิดขึ้นเมื่อขอบมีต้นทุนติดลบหรือขอบน้ำหนักติดลบเท่านั้น
Dijkstra ล้มเหลวในการคำนวณเส้นทางที่สั้นที่สุดระหว่างสองโหนดในสถานการณ์นี้ เป็นผลให้อัลกอริทึมนี้มีข้อเสียบางประการ เพื่อแก้ปัญหาขอบลบนี้ จึงมีการใช้อัลกอริธึมอื่นที่เรียกว่า "อัลกอริธึม Bellman-Ford" อัลกอริทึมนั้นสามารถทำงานกับขอบลบได้
ความซับซ้อนของอัลกอริทึมของ Dijkstra
การใช้งานข้างต้นใช้ลูป "for" สองอัน ลูปเหล่านี้ทำงานตามจำนวนจุดยอด ดังนั้น ความซับซ้อนของเวลาคือ โอ(วี2)- ในที่นี้คำว่า "0" หมายถึงสัญลักษณ์ที่ให้ข้อสันนิษฐานสำหรับอัลกอริทึม Dijkstra
เราสามารถจัดเก็บกราฟโดยใช้ "คิวลำดับความสำคัญ" คิวลำดับความสำคัญคือโครงสร้างข้อมูลฮีปไบนารี มันจะมีประสิทธิภาพมากกว่าเมทริกซ์ 2 มิติ ความได้เปรียบที่มีต้นทุนขั้นต่ำจะมีลำดับความสำคัญสูง
แล้วความซับซ้อนของเวลาก็จะเป็น O(E บันทึก(V))- โดยที่ E คือจำนวนขอบ และ V คือจำนวนจุดยอด
ความซับซ้อนของพื้นที่คือ โอ(วี2)เนื่องจากเราใช้เมทริกซ์คำคุณศัพท์ (อาร์เรย์ 2 มิติ) ความซับซ้อนของพื้นที่สามารถปรับให้เหมาะสมได้โดยใช้โครงสร้างข้อมูลแบบรายการที่อยู่ติดกันหรือคิว
