อัลกอริทึมของ 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

การสาธิตตาราง 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" สองอัน ลูปเหล่านี้ทำงานตามจำนวนจุดยอด ดังนั้น ความซับซ้อนของเวลาคือ โอ(วี²)- ในที่นี้คำว่า "0" หมายถึงสัญลักษณ์ที่ให้ข้อสันนิษฐานสำหรับอัลกอริทึม Dijkstra

เราสามารถจัดเก็บกราฟโดยใช้ "คิวลำดับความสำคัญ" คิวลำดับความสำคัญคือโครงสร้างข้อมูลฮีปไบนารี มันจะมีประสิทธิภาพมากกว่าเมทริกซ์ 2 มิติ ความได้เปรียบที่มีต้นทุนขั้นต่ำจะมีลำดับความสำคัญสูง

แล้วความซับซ้อนของเวลาก็จะเป็น O(E บันทึก(V))- โดยที่ E คือจำนวนขอบ และ V คือจำนวนจุดยอด

ความซับซ้อนของพื้นที่คือ โอ(วี²)เนื่องจากเราใช้เมทริกซ์คำคุณศัพท์ (อาร์เรย์ 2 มิติ) ความซับซ้อนของพื้นที่สามารถปรับให้เหมาะสมได้โดยใช้โครงสร้างข้อมูลแบบรายการที่อยู่ติดกันหรือคิว