เทคนิคการหาเส้นทางที่สั้นที่สุด (Shortest Path Algorithms) เป็นวิธีการหาเส้นเชื่อมระหว่างโหนดเริ่มต้น และโหนดสิ้นสุดในกราฟที่ให้ผลรวมของค่าน้ำหนักของเส้น (Edge Weight) ที่ต่ำที่สุด
For English, please follow this article on Medium.
เทคนิคเหล่านี้นำไปใช้งานทางด้าน
- การเชื่อมต่อเครือข่าย Network
- การเดินทาง และการจัดการจราจร
- การหาเส้นทางการบิน
- การออกแบบอุปกรณ์ Electronic กับการออกแบบชิบ VLSI (Very-large-scale integration)
- เครือข่ายสังคมออนไลน์ (Social Network)
เทคนิคที่ค้นหา Shortest Path ในบทความนี้เราจะกล่าวถึง 2 เทคนิค ได้แก่ Dijkstra และ Bellman-Ford Algorithms
แต่ก่อนที่เราจะเข้าไปยังรายละเอียดของแต่ละเทคนิค เรามาเริ่มต้นด้วยข้อมูลเบื้องต้นของกราฟว่ากราฟมันคืออะไร?
สารบัญ
กราฟ (Graph)
กราฟ [1] เป็นโครงสร้างข้อมูลที่ไม่เป็นเชิงส้น (Non-linear) ที่ประกอบไปด้วยโหนด (Node หรือ Vertex (V)) และเส้น (Line หรือ Edge (E)) ที่เชื่อมระหว่างโหนดสองโหนด
กราฟสามารถแบ่งประเภทได้ตามค่าน้ำหนัก (Weight) กับตามทิศทาง (Direction) และตาม Graph Representation
แบ่งตาม Weight
การแบ่งประเภทกราฟตาม Weight นั้นมีทั้งหมด 2 ประเภท
- กราฟที่ไม่ระบุค่าน้ำหนัก (Unweighted Graph) ที่สามารถแทนได้ด้วย G(V, E) กราฟในลักษณะนี้จะไม่มีค่า Weight ที่กำหนดไว้บนเส้นของกราฟ
- กราฟที่ระบุค่าน้ำหนัก (Weighted Graph) ที่แทนได้ด้วย G(V, E, W) กราฟในลักษณะนี้จะได้รบการกำหนดค่า Weight (ค่า W) ไว้บนเส้นของกราฟ
แบ่งตาม Direction
การแบ่งประเภทกราฟตาม Direction นั้นมีทั้งหมด 2 ประเภท
- กราฟที่ไม่ระบุทิศทาง (Undirected Graph) กราฟประเภทนี้จะอนุญาตให้ตัว Algorithm สามารถเดินทางไป-กลับบนเส้นของกราฟได้
- กราฟที่ระบุทิศทาง (Directed Graph) กราฟชนิดนี้จะระบุทิศทางไว้บนกราฟเพื่อกำหนดทิศทางการเดินของเส้นของกราฟ
แบ่งตาม Graph Representation
กราฟสามารถแทนได้ด้วยการใช้ Adjacency Matrix กับ Adjacency List
Adjacency Matrix เป็นการกำหนดตัวแปรให้อยู่ในรูป Array ซ้อน Array (Nested Array) ที่เป็นตัวแปรประเภท Integer หรือ Boolean โดย
- กราฟที่ไม่ได้ระบุค่า Weight (Unweighted Graph): เราจะกำหนดให้ในกรณีที่โหนดไม่ได้เชื่อมไปยังโหนดอื่นนั้นมีค่าเท่ากับ 0 แต่กรณีที่ได้เชื่อมไปยังอีกโหนด เราจะกำหนดให้มีค่าเท่ากับ 1
- กราฟที่ระบุค่า Weight (Weighted Graph): เราจะกำหนดให้ในกรณีที่โหนดไม่ได้เชื่อมไปยังโหนดอื่นมีค่าเท่ากับ 0 แต่กรณีที่เชื่อมไปยังโหนดอื่น เราจะกำหนดให้มีค่าบนเส้นนั้นมีค่ามากกว่า 0 (หรือน้อยกว่า 0 ก็ได้) ขึ้นกับว่าเราจะกำหนดค่าน้ำหนัก (Weight) ของเส้นนั้นมีค่าเท่าไร
เราสามารถดูตัวอย่างได้ตามด้านล่างนี้
Adjacency List เป็นการกำหนดตัวแปรให้อยู่ในรูป Array ที่มี Linked List เพื่อกำหนดว่าโหนดนั้นเชื่อมไปยังโหนดอื่นหรือไม่ โดย
- กราฟที่ไม่ได้ระบุค่า Weight (Unweighted Graph): เราจะไม่ได้กำหนด Weight ลงไปใน Node ของ Linked List
- กราฟที่ระบุค่า Weight (Weighted Graph): เราจะกำหนดค่า Weight ลงไปใน Node ของ Linked List นั้น ๆ
เราสามารถดูตัวอย่างได้ตามด้านล่างนี้
หลังจากที่ทราบข้อมูลเบื้องต้นที่เกี่ยวกับกราฟแล้ว เรามาดูเทคนิคที่เกี่ยวข้องกับการหา Shortest Path ได้แก่ Dijkstra’s and Bellman-Ford’s algorithms
Dijkstra’s Algorithm
Dijkstra’s algorithm [2, 3] เป็นเทคนิคการหา Shortest Path ที่มีประโยชน์ และได้รับความนิยมสำหรับการหาเส้นทางที่สั้นที่สุดจากโหนดเริ่มต้นไปยังโหนดปลายทางโดยใช้สำหรับกราฟที่ไม่มีค่าน้ำหนักบนเส้น Edge ที่มีค่าเป็นลบ (Negative Edge Weight)
เทคนิคนี้ได้รับการตั้งชื่อตามนักวิจัยชาว Dutch ที่มีชื่อว่า Edsger W. Dijkstra
ขั้นตอนการทำงาน
ขั้นตอนแรก เรากำหนดให้
- โหนดเริ่มต้นเป็นโหนดที่ 1
- ระยะทาง (distance) ในโหนดที่ 1 มีค่าเท่ากับ 0 ส่วนโหนดอื่นกำหนดให้มีค่าเท่ากับ Infinity
- ตัวแปรเพื่อแสดงว่าเราไปยังโหนดนั้น ๆ แล้ว (Visited) มีค่าเท่ากับ False
ขั้นตอนที่สอง เราพิจารณาจากโหนดปัจจุบัน เพื่อดูโหนดข้างเคียงตามเส้นเชื่อมทุกโหนดที่ยังไม่ได้ไปเยือน และคำนวณหาระยะทางต่อเชื่อมจากเส้นเชื่อม เพื่อดูว่าค่าที่ได้มีค่าน้อยที่สุดหรือไม่ ในกรณีที่ค่านั้นมีค่าน้อยที่สุด ให้เราอัพเดทระยะทางใหม่ด้วยค่าที่เราคำนวณได้
หลังจากนั้น เรากำหนดให้โหนดปัจจุบันที่เราเข้าไปแล้วให้มีค่า Visited เท่ากับ True เพื่อแสดงให้เห็นว่าเราไปเยือนโหนดนั้น ๆ เรียบร้อย
เราแสดงตัวอย่างการพิจารณาในแต่ละโหนดได้ตามขั้นตอนตามด้านล่างนี้
หนึ่ง เราพิจารณาในโหนดที่ 1 ด้วยการคำนวณระยะทาง (Distance) จากโหนดที่ 1 ไปยังโหนดข้างเคียง ได้แก่โหนดที่ 2 และ 3 โดยคำนวณได้ตามด้านล่างนี้
- Distance of 2 = (Distance of 1) + (Weight from 1 to 2) = 0 + 3 = 3
- Distance of 3 = (Distance of 1) + (Weight from 1 to 3) = 0 + 2 = 2
ผลลัพธ์การคำนวณระยะทางจากโหนดที่ 1 ไปโหนดที่ 2 และ 3 มีค่าเท่ากับ 3 และ 2 ตามลำดับ ซึ่งมีค่าน้อยกว่า infinity ให้เรานำค่านั้นไปอัพเดทในตาราง และกำหนดให้โหนดที่ 1 ได้รับการเยือนเรียบร้อย (ด้วยกำหนด Visited ให้เป็น True)
สอง เราพิจารณาในโหนดข้างเคียงที่เชื่อมจากโหนดที่ 1 โดยเราพิจารณาในโหนดที่ 2 ก่อน
โหนดนี้จะมีโหนดที่เชื่อมต่อจากโหนดที่ 2 เพียงโหนดเดียว คือโหนดที่ 3 ให้เราคำนวณหาระยะทางโดยการนำค่าที่ได้จากขั้นตอนก่อนหน้า มาบวกกับระยะทางระหว่างระหว่างโหนดที่ 2 และ 3
การคำนวณแสดงได้ตามด้านล่างนี้
- Distance of 3 = (Distance of 2) + (Weight from 2 to 3) = 3 + 2 = 5
ผลลัพธ์ที่ได้จะมีค่าเท่ากับ 5 ซึ่งมีค่ามากกว่าผลลัพธ์ที่ได้จากการคำนวณในขั้นตอนก่อนหน้าที่หาระยะทางระหว่างโหนดที่ 1 และโหนดที่ 3 ดังนั้นแล้ว เราจะไม่อัพเดทค่านี้ในตาราง
ต่อมาเรากำหนดให้โหนดที่ 2 ได้รับการเยือนเรียบร้อย (ด้วยกำหนด Visited ให้เป็น True)
สาม เราพิจารณาในโหนดข้างเคียงที่เชื่อมจากโหนดที่ 1 อีกโหนดหนึ่ง คือโหนดที่ 3
โหนดนี้จะมีโหนดที่เชื่อมต่อจากโหนดที่ 3 เพียง 2 โหนด คือโหนดที่ 4 และโหนดที่ 5 ให้เราคำนวณหาระยะทางโดยการนำค่าที่ได้จากขั้นตอนก่อนหน้า มาบวกกับระยะทางระหว่างระหว่างโหนดที่ 3 กับโหนดที่เชื่อมต่อกัน
การคำนวณแสดงได้ตามด้านล่างนี้
- Distance of 4 = (Distance of 3) + (Weight from 3 to 4) = 2 + 4 = 6
- Distance of 5 = (Distance of 3) + (Weight from 3 to 5) = 2 + 3 = 5
ผลลัพธ์การคำนวณระยะทางจากโหนดที่ 3 ไปโหนดที่ 4 และ 5 มีค่าเท่ากับ 6 และ 5 ตามลำดับ ซึ่งมีค่าน้อยกว่า infinity ให้เรานำค่านั้นไปอัพเดทในตาราง และกำหนดให้โหนดที่ 3 ได้รับการเยือนเรียบร้อย (กำหนด Visited ให้เป็น True)
สี่ เราพิจารณาในโหนดข้างเคียงที่เชื่อมจากโหนดที่ 3 โดยเราพิจารณาในโหนดที่ 4 ก่อน
โหนดนี้จะมีโหนดที่เชื่อมต่อจากโหนดที่ 4 เพียงโหนดเดียว คือโหนดที่ 5 ให้เราคำนวณหาระยะทางโดยการนำค่าที่ได้จากขั้นตอนก่อนหน้า มาบวกกับระยะทางระหว่างระหว่างโหนดที่ 4 และ 5
การคำนวณแสดงได้ตามด้านล่างนี้
- Distance of 5 = (Distance of 4) + (Weight from 4 to 5) = 6 + 3 = 9
ผลลัพธ์ที่ได้จะมีค่าเท่ากับ 9 ซึ่งมีค่ามากกว่าผลลัพธ์ที่ได้จากการคำนวณในขั้นตอนก่อนหน้าที่หาระยะทางระหว่างโหนดที่ 3 และโหนดที่ 5 ดังนั้นแล้ว เราจะไม่อัพเดทค่านี้ในตาราง
ต่อมาเรากำหนดให้โหนดที่ 4 ได้รับการเยือนเรียบร้อย (Visited เท่ากับ True)
ห้า เราพิจารณาในโหนดข้างเคียงที่เชื่อมจากโหนดที่ 3 อีกโหนดหนึ่ง คือโหนดที่ 5
โหนดนี้จะไม่มีโหนดที่เชื่อมต่อจากโหนดที่ 5 เลย ดังนั้น เราไม่จำเป็นต้องคำนวณอะไรในโหนดนี้อีก
สุดท้าย เราจะได้ Shortest Path โดยเดินจากโหนดที่ 1 ผ่านโหนดที่ 3 ไปยังโหนดที่ 5 โดยการแสดงภาพตามด้านล่างนี้
เขียนโค้ดด้วย Python
def djikstra_algorithm(distance, start = 0, final = 5):
visited, dist_table = [], []
for i in range(final + 1):
visited.append(False)
dist_table.append([float('inf'), None])
queue = [start]
dist_table[start][0] = 0
while len(queue) > 0:
vertex = queue.pop(0)
visited[vertex] = True
dist_previous, parent_previous = dist_table[vertex]
for idx, dist_each in enumerate(distance[vertex]):
if visited[idx] or dist_each == 0:
continue
if (dist_each + dist_previous) < dist_table[idx][0]:
dist_table[idx][0] = dist_each + dist_previous
dist_table[idx][1] = vertex
queue.append(idx)
vertex = dist_table[final]
path = [final]
distance = vertex[0]
parent = vertex[1]
while parent is not None:
vertex = dist_table[parent]
path.append(parent)
parent = vertex[1]
return pathเขียนโค้ดด้วย JavaScript
function djikstra_algorithm(distance, start = 0, final = 5)
{
let dist_table = [], visited = [];
for(let i = start; i <= final; i++) {
dist_table.push([Infinity, null]);
visited.push(false);
}
let queue = [start]
dist_table[start] = [0, null];
while(queue.length > 0) {
let vertex = queue.shift();
let [dist_current, parent] = dist_table[vertex];
visited[vertex] = true;
for(let target = 0; target < distance.length; target++) {
let weight = distance[vertex][target];
if((!visited[target] && weight > 0) && (dist_current + weight < dist_table[target][0]) ) {
dist_table[target] = [
dist_current + weight, vertex
];
queue.push(target);
}
}
}
let [dist, prev] = dist_table[final];
let path = [final];
while(prev != null) {
path.push(prev);
[dist, prev] = dist_table[prev];
}
return path;
}Computational Complexity
Time Complexity ของ Algorithm นี้ด้วย
- การใช้ Adjacency Matrix มีค่าเท่ากับ O(V^2)
- การใช้ Adjacency List มีค่าเทา่กับ O(E log V)
ส่วน Space Complexity ของ Algorithm นี้มีค่าเท่ากับ O(V)
สำหรับรายละเอียดเกี่ยวกับ Time Complexity, Space Complexity และตัว Big-O อ่านได้ที่บทความที่แล้ว
Bellman-Ford Algorithm
Bellman-Ford Algorithm [4] เป็นเทคนิคในการหา Shortest Path อีกเทคนิคหนึ่งที่มีลักษณะการทำงานคล้ายกันกับ Dijkstra’s Algorithm แต่มีข้อแตกต่างอยู่ โดย Bellman-Ford Algorithm รองรับ
- กราฟที่เป็น Unweighted กับ Weighted graphs
- การตรวจสอบว่ากราฟเป็นมี Negative Cycle หรือไม่ ถ้ามีผลลัพธ์การคำนวณจะมีค่าลดลงไปเรื่อย ๆ จนเกิดเป็นการวนลูปไม่มีที่สิ้นสุด (Indefinite Loop)
ขั้นตอนการทำงาน
ขั้นตอนแรก เรากำหนดให้โหนดเริ่มต้น (Source ที่แสดงเป็นวงกลมสีเขียวตามภาพด้านล่างนี้) มีค่าระยะทาง (Distance) เท่ากับ 0 ส่วนโหนดอื่นมีค่าเท่ากับ Infinity
ต่อมา เราหา Shortest Path ในกราฟ โดยกราฟมีโหนดทั้งหมด N โหนด ให้เราคำนวณ Distance บริเวณโหนดเริ่มต้นเสียก่อน จากนั้นประมวลผลในทุกโหนด [edges(u, v, weight)] เพื่อหา Shortest Path ทั้งหมด N-1 ครั้ง ด้วยการคำนวณตามฟังก์ชัน dist[v] = minimum(dist[v], distance[u] + weight)
ขั้นตอนการประมวลผลแสดงรายละเอียดตามด้านล่างนี้
หนึ่ง คำนวณ Distance ในโหนดที่ 1 โดยในโหนดนี้จะเชื่อมต่อไปอีก 2 โหนด ได้แก่ โหนดที่ 2 และโหนดที่ 3
เราสามารถคำนวณหาระยะทางระหว่างโหนดปัจจุบันกับโหนดที่เชื่อมต่อกันได้ตามด้านล่างนี้
- Distance of 2 = (Distance of 1) + (Weight from 1 to 2) = 0 + 3 = 3
- Distance of 3 = (Distance of 1) + (Weight from 1 to 3) = 0 + 2 = 2
ค่าที่ได้จากการคำนวณจากโหนดที่ 1 ไปโหนดที่ 2 และ 3 มีค่าน้อยกว่า Infinity ดังนั้น เราจะอัพเดท Distance ลงไปในตาราง
สอง คำนวณ Distance ในโหนดที่ 2 โดยในโหนดนี้จะเชื่อมต่อไปอีก 1 โหนด คือโหนดที่ 3
การคำนวณระยะทางของโหนดนี้เราทำได้โดยเอาค่าการคำนวณระยะทางจากจากโหนดเริ่มต้น มายังโหนดปัจจุบัน (โหนดที่ 1 มายังโหนดที่ 2) มาบวกกับระยะทางระหว่างโหนดปัจจุบันกับโหนดที่เชื่อมกันอยู่
การคำนวณทำได้ตามด้านล่างนี้
- Distance of 3 = (Distance of 2) + (Weight from 2 to 3) = 3 + 2 = 5
ค่าที่ได้จากการคำนวณจากโหนดที่ 2 ไปโหนดที่ 3 มีค่ามากกว่าการคำนวณจากข้อที่แล้ว ดังนั้นเราจะไม่อัพเดทค่านี้ลงไปในตาราง
สาม คำนวณ Distance ในโหนดที่ 3 โดยในโหนดนี้จะเชื่อมต่อไปอีก 2 โหนด ได้แก่โหนดที่ 4 และ 5
การคำนวณทำได้ตามด้านล่างนี้
- Distance of 4 = (Distance of 3) + (Weight from 3 to 4) = 2 + 4 = 6
- Distance of 5 = (Distance of 3) + (Weight from 3 to 5) = 2 + 3 = 5
ค่าที่ได้จากการคำนวณ ไปโหนดที่ 4 และ 5 มีค่าน้อยกว่า Infinity ดังนั้นเราจะอัพเดทค่าเหล่านี้ลงไปในตาราง
สี่ คำนวณ Distance ในโหนดที่ 4 โดยในโหนดนี้จะเชื่อมต่อไปอีก 1 โหนด คือโหนดที่ 5
การคำนวณทำได้ตามด้านล่างนี้
- Distance of 5 = (Distance of 4) + (Weight from 4 to 5) = 6 + 3 = 9
ค่าที่ได้จากการคำนวณมีค่ามากกว่าการคำนวณจากข้อที่ผ่านมา ดังนั้นเราจะไม่อัพเดทค่านี้ลงไปในตาราง
หลังจากที่วนลูปเข้าไปดูในแต่ละโหนดของกราฟตามขั้นตอนที่กล่าวมาข้างบนนี้เรียบร้อยแล้ว เรามาวนลูปอีกรอบหนึ่งเพื่อมองหา Negative Cycle ในกราฟว่ามีหรือไม่?
เหตุผลของการวนลูปเข้าไปในกราฟอีกรอบหนึ่งเพื่อคำนวณระยะทางอีกรอบ แล้วตรวจสอบว่าระยะทางที่ผ่านการคำนวณนั้นสั้นกว่าที่เราได้บันทึกในตารางหรือไม่ ถ้าใช่ แสดงว่าเราพบ Negative Cycle ในกราฟ
เขียนโค้ดด้วย Python
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def add(self, source, destination, weight):
self.graph.append([
source, destination, weight
])
def bellmanford(self, source):
distance = [float('inf') for i in range(self.V)]
previous = [None for i in range(self.V)]
distance[source] = 0
for _ in range(self.V - 1):
for s, d, w in self.graph:
if distance[s] != float('inf') and distance[s] + w < distance[d]:
distance[d] = distance[s] + w
previous[d] = s
for s, d, w in self.graph:
if distance[s] + w < distance[d]:
print("Error: Negative Cycle Exists")
return None, None
return distance, previous
if __name__ == '__main__':
g = Graph(5)
g.add(0, 1, 5)
g.add(0, 2, 4)
g.add(1, 3, 3)
g.add(2, 1, 6)
g.add(3, 2, 2)
distance, previous = g.bellmanford(0)
for i, (d, p) in enumerate(zip(distance, previous)):
print(i, d, p)เขียนโค้ดด้วย JavaScript
class Graph
{
constructor(vertex)
{
this.vertex = vertex;
this.graph = [];
}
add(source, destination, value)
{
this.graph.push([
source, destination, value
]);
}
bellmanford(source)
{
let distance = [], previous = [];
for(let i = 0; i < this.vertex; i++) {
distance.push(Infinity);
previous.push(null);
}
distance[source] = 0;
let target_loop_range = this.vertex - 1;
for(let i = 0; i < target_loop_range; i++) {
for(let [s, d, weight] of this.graph) {
if(distance[s] != Infinity &&
distance[s] + weight < distance[d]) {
distance[d] = distance[s] + weight;
previous[d] = s;
}
}
}
for(let [s, d, weight] of this.graph) {
if(distance[s] + weight < distance[d]) {
console.error("Error: Negative Cycle Exists");
return [null, null];
}
}
return [distance, previous];
}
}
g = new Graph(5);
g.add(0, 1, 5);
g.add(0, 2, 4);
g.add(1, 3, 3);
g.add(2, 1, 6);
g.add(3, 2, 2);
let [distance, previous] = g.bellmanford(0);
if(distance && previous) {
for(let i = 0; i < distance.length; i++) {
let d = distance[i],
p = previous[i];
console.log(`${ i }: ${ d }, ${ p }`);
}
}Computational Complexity
Time Complexity ของ Algorithm นี้ในกรณีที่เป็น
- Best case: เมื่อค่าระยะทางที่คำนวณได้หลังจากที่วนลูปที่ 1 และ 2 มีค่าเท่ากันแล้ว เราจะได้ค่าเท่ากับ O(E)
- Average กับ Worst Case: มีค่าเท่ากับ O(VE)
ส่วน Space Complexity ของ Algorithm นี้มีค่าเท่ากับ O(V)
สรุป
เทคนิคการหาเส้นทางที่สั้นที่สุด (Shortest Path Algorithms) เป็นวิธีการหาเส้นเชื่อมระหว่างโหนดเริ่มต้น และโหนดสิ้นสุดในกราฟที่ให้ผลรวมของค่าน้ำหนักของเส้น (Edge Weight) ที่ต่ำที่สุด
เทคนิคที่เราได้กล่าวถึงในบทความนี้ก็ได้แก่ Dijkstra กับ Bellman-Ford Algorithms ที่มีความคล้ายคลึงกัน แต่ Bellman-Ford Algorithm รองรับการจัดการกับกราฟที่มี Negative Edge Weight และ Negative Cycle ครับ
สำหรับผู้อ่านที่เห็นว่าบทความนี้ดี มีประโยชน์ ให้กดไลค์ หรือกดแชร์ไปยังแพลตฟอร์มโซเชียลต่าง ๆ นอกจากนี้ ผู้อ่านยังติดตามได้่ใน Linkedin หรือ X (หรือ Twitter) ได้ครับ
