กราฟอัลกอริธึม
กราฟอัลกอริธึม
กราฟประกอบด้วยเซ็ตของจุดและด้าน
จุดคือ Vertice และด้านคือ Edge เขียนในลักษณะเซ็ตของคณิตศาสตร์ได้เป็น
G
= (V, E)
โดยสมมุติว่า G
คือกราฟ 1 ตัว และ V คือ
เซ็ตของ Vertice ส่วน E คือเซ็ตของ Edge
บางครั้งเราจะเรียก edge ว่าเป็น
arc ถ้าคู่อันดับมีการจัดเรียงกันมาตามลำดับและมีทิศทาง (directed)
กราฟแบบที่แต่ละเส้นมีทิศทางกำกับไว้ เราจะเรียกว่า Directed
Graph หรือย่อๆคือ digraphs
สมมุติว่ามีจุดมุม Vertex
อยู่จุดหนึ่ง ชื่อว่า w เราบอกว่าจุด w
นี้ต่อติด (adjacent) กับจุด v ก็ต่อเมื่อ (w, v) Î E
แต่ถ้ากราฟนี้เป็นแบบไม่มีทิศทาง เส้น (w,
v) ย่อมเทียบเท่ากับเส้น (v, w) ดังนั้นถ้า w
adjacent to v ดังนั้น v ก็ย่อมจะ adjacent
to w ด้วย หรือพูดง่ายๆก็คือมันต่อติดกันทั้งขาไปและขากลับเพราะไม่สนใจทิศทางนั่นเอง
บางครั้งบนเส้นแต่ละเส้นจะมีตัวเลขบอกน้ำหนักเอาไว้เราเรียกว่า
weight หรือ cost โดยนำไปใช้แทนระยะทาง
หรือ น้ำหนัก หรือ จำนวนเงิน หรือ คะแนน ก็ได้แล้วแต่การนำไปใช้งาน
รูปภาพ 2 ตัวอย่างเส้น (Edge) แบบไม่มีทิศทาง แบบมีทิศทาง และแบบบอกค่าน้ำหนัก
Path
พาธ (Path) เป็นทางเดินผ่านจุดแต่ละจุดไปบนกราฟ
ดังนั้น path จึงเป็นลำดับของจุดที่เดินผ่านไป เช่น w1,
w2, w3, …, wn โดย w ทั้งหมดนี้เป็นสมาชิกของ V และเส้นที่เดินผ่านคือ (wi,
wi+1) Î E
Length
ความยาวของ path เรียกว่า length
ก็คือจำนวนของเส้นที่อยู่ใน path ตัวอย่างเช่นรูปภาพ
3 จะมี length
เป็น 3 เนื่องจากบนทางเดินมีเส้นประกอบกันอยู่
3 เส้น
หากเราเริ่มต้นที่จุดจุดหนึ่ง
และเดินย่ำอยู่ที่จุดเดิม path จะมี length เป็น 0 เราจะใช้ path พิเศษนี้เพื่อประโยชน์บางอย่าง
ซึ่งจะกล่าวถึงในภายหลัง
Loop
ถ้าใน path มีเส้นที่เป็นคู่ลำดับ (v, v) คือหมายถึงเดินย่ำอยู่ที่จุดเดิม
บางครั้งเราเรียก path ประเภทนี้ว่า loop
รูปภาพ 4 ตัวอย่างของ path ที่เป็น loop
กราฟที่เราศึกษากันจะไม่มี loop (หรือเรียกว่าเป็น loopless)
Simple Path
หมายถึงเส้นทางที่เดินผ่านจุดที่ไม่ทับกับจุดเดิมเลย
ยกเว้นเฉพาะจุดสุดท้ายที่อาจจะเป็นจุดตั้งต้นได้ ตัวอย่างของ Simple Path เช่น {a, b, c} หรือ {a, b, c, a} แต่ตัวอย่างที่ไม่เป็น Simple Path เช่น {a,
b, c, b, a} เป็นต้น
รูปภาพ 5 แสดงตัวอย่างของ Simple Path และที่ไม่เป็น Simple Path
Cycle
ถ้าเป็นกราฟแบบมีทิศทาง
จะเป็นเส้นทางที่สุดท้ายวนกลับมาที่จุดเริ่มต้น แต่ไม่ใช่ลูป คืออย่างน้อยจะต้องมี
length เป็น 1
ถ้าระหว่างทางที่เดินไปไม่มีการทับจุดที่เคยเดินผ่านไปแล้ว แบบนี้ถือว่าเป็นทั้ง Simple
Path และ Cycle แต่ถ้าเส้นทางเดินที่ผ่านไปสุดท้ายวนกลับมาที่จุดเริ่มต้น
แต่มีการทับจุดเดิม อย่างนี้ถือว่าเป็นแค่ Cycle อย่างเดียวไม่เป็น
Simple Path
รูปภาพ 6
ตัวอย่างของ Loop , Cycle และ Cycle ที่เป็น Simple Path
ถ้าเป็นกราฟแบบไม่มีทิศทาง การย้อนกลับในเส้นทางเดียวกันไม่ถือเป็น
Cycle เพราะทับเส้นทางเดิม เช่น (u, v) และ (v, u) ไม่ถือว่าเป็น Cycle ในกรณีของกราฟแบบไม่มีทิศทาง เพราะเป็นเส้นเดียวกัน
รูปภาพ 7 ตัวอย่างของ
Cycle ในกรณีของ Undirected Graph
DAG
ย่อมาจากคำว่า Directed Acyclic Graph คือกราฟแบบมีทิศทาง ที่ไม่มี Cycle อยู่ข้างในเลย
ดังนั้นใน DAG จะต้องไม่มีเส้นทางเดินที่ย้อนกลับมาทางเก่าได้
เรียกว่าเมื่อเลือกเดินทางใดทางหนึ่งแล้วจะได้เส้นทางเดียว ดังนั้น DAG มักจะนำมาใช้ในการทำแผนผังการตัดสินใจ เช่น โครงสร้างบุพวิชา (Prerequisite)
หรือโครงสร้างการสืบทอด (Inheritance Hierarcy) เป็นต้น
รูปภาพ 8 ตัวอย่างของ acycle graph และที่ไม่เป็น acyclic graph
Connected
ถ้าเป็นกราฟแบบไม่มีทิศทาง เราจะเรียกว่าเป็น Connected ถ้ามีเส้นทางเดินถึงกันหมดทุกจุด แต่ถ้าเป็นกราฟแบบมีทิศทางและเกิดเส้นทางที่เดินถึงกันได้ทุกจุดแบบนี้เราเรียกว่า
Strongly Connected
รูปภาพ 9
กรณีที่เป็น Undirected Graph มีคุณสมบัติ Connected
กรณีที่เป็น Undirected Graph และมีคุณสมบัติ Connected จะเป็นดังนี้
รูปภาพ 10 กรณีที่เป็น
Strongly Connected
สำหรับกราฟที่มีทิศทาง
ถ้าไม่มีเส้นเชื่อมโยงครบหมดทุกจุด
แต่มีบางส่วนของกราฟที่เชื่อมโยงครบทุกจุดในกลุ่มนั้น เราเรียกว่าเป็น Weakly
Connected และถ้ากราฟใดๆที่มีเส้นเชื่อมทุกจุดเราเรียกว่าเป็น Complete
Graph
ตัวอย่างของกราฟคือ ระบบการบินและสนามบิน
โดยสมมุติว่าสนามบินแต่ละแห่งคือจุดหนึ่งจุดบนกราฟ
และเส้นเชื่อมระหว่างจุดคือเส้นทางการบินที่สามารถบินจากสนามบินหนึ่งไปอีกที่หนึ่งได้
และแต่ละเส้นทางอาจจะมีค่าน้ำหนักที่เป็นไปได้หลายอย่าง เช่น ระยะเวลา ระยะทาง
ต้นทุน หรือ ชื่อเที่ยวบิน (Flight)
9.1.1 การแทนข้อมูลกราฟด้วยตาราง
การแทนข้อมูลกราฟด้วยตารางมีวิธีอยู่ 2 วิธีคือ Adjacency Matrix และ Adjacency List
ตัวอย่างเช่น กราฟดังต่อไปนี้
เราสามารถเขียน Adjacency Matrix ได้ดังนี้
และสามารถเขียนเป็น Adjacency List ได้ดังนี้
ถ้าใช้วิธีแบบ Adjacency Matrix จะง่ายต่อการเก็บและค้นหาข้อมูล เพราะเป็นแค่ตารางอะเรย์ 2 มิติ แต่มีปัญหาคือถ้ากราฟมีจำนวนเส้นเชื่อมน้อย (เรียกว่ามัน sparse)
จะทำให้เปลืองพื้นที่มาก แต่สำหรับวิธีการ Adjacency List จะไม่เปลืองพื้นที่เก็บข้อมูล แต่มีข้อเสียคือ
เก็บและค้นหาข้อมูลยากกว่าเล็กน้อย
9.2 Topological Sort
เป็นวิธีการจัดเรียงลำดับการเข้าถึงจุดแต่ละจุดใน Directed
Acyclic Graph (DAG) ตัวอย่างเช่น
หากมีโครงสร้างหลักสูตรที่จำเป็นต้องลำดับการเรียงลำดับว่าจะเรียนวิชาไหนก่อนหลัง
เช่น ภาพต่อไปนี้
แสดงให้เห็นว่าหาก นักศึกษา ต้องการเรียนวิชา CS313
นักศึกษาจะต้องผ่านวิชา MA111, CS105, CS211 และ
CS212 มาก่อนจึงจะมาลงเรียนวิชา CS313 ได้
ภาพกราฟข้างต้นนี้คือ Directed Acyclic
Graph และหากเราจำเป็นต้องหาว่ามีการเรียงลำดับอย่างไรจึงจะไล่จนครบทุกวิชา
เราจำเป็นต้องใช้อัลกอริธึมของ Topological Sort โดยทำดังนี้
1. หาว่าจุดไหนที่มี indegree เป็น 0 คือจุดที่ไม่มีเส้นพุ่งเข้าเลย และนับจุดนั้นเป็นหมายเลข 1
2. ให้ตัดจุดที่มี indegree เป็น 0 ออกไปจากกราฟ และทำต่อไปเรื่อยๆ ตามวิธีข้อ 1 จนครบทุกจุด
สมมุติกราฟ DAG ที่มี 7
จุดดังนี้
เราจะเรียงลำดับแบบ Topological Sort โดยหาจุดที่มี indegree = 1 ในที่นี้คือจุด
v1 เพราะไม่มีเส้นพุ่งเข้า v1 เลยแม้แต่เส้นเดียว
ให้นับ v1 เป็นลำดับที่ 1
และเมื่อตัด v1 ออกไปจากกราฟ
จะได้กราฟที่เหลือ indegree เป็นภาพด้านซ้ายดังนี้
ค้นหาต่อไปว่าจุดไหนที่มี indegree = 0 พบว่าจุด v2 มี indegree = 0 ดังนั้นลำดับต่อไปคือ
v2 ให้นับ v2 เป็นหมายเลข 2 และตัด v2 ออกจากกราฟจะได้ภาพต่อมาเป็นดังนี้
ตัวถัดไปที่มี indegree = 0 คือ
v5 เรานับ v5 เป็นหมายเลข 3 และตัด v5 ออกจากกราฟจะได้ภาพดังนี้
ตัดถัดไปที่มี indegree = 0 คือ
v4 เรานับ v4 เป็นหมายเลข 4 และตัด v4 ออกจากกราฟจะได้ภาพดังนี้
ตัดถัดไปที่มี indegree = 0 คือ
v3 และ v7 แสดงว่าลำดับต่อมาเราสามารถนับ
v3 เป็นหมายเลข 5 หรือนับ v7 เป็นหมายเล 5 ก็ได้เช่นกัน
ในกรณีที่เราต้องเลือกตัวใดตัวหนึ่ง ในที่นี้ขอเลือก v3 เป็นหมายเลข
5 และตัด v3 ออกไปจะได้ภาพดังนี้
และตัดถัดมาที่มี indegree = 0 คือ v7 เรานับ v7 เป็นหมายเลข 6
และตัด v7 ออกจากกราฟจะได้ภาพดังนี้
ตัวสุดท้ายที่เหลืออยู่ในกราฟ คือ v6 มี indegree = 0 ดังนั้นเรานับ v6 เป็นหมายเลข 7 และตัดออกจากกราฟจะได้ภาพสุดท้ายดังนี้
จากภาพข้างต้นเราสามารถอธิบายขึ้นตอนได้ด้วยกรรมวิธีการเก็บข้อมูลลงตารางที่รูปแบบดังนี้
สังเกตจากตารางจะพบว่าเราเอา v1 ไปเข้าคิวเพราะ v1 เป็นจุดที่มี indegree =
0 และเมื่อเราทำงานรอบถัดมาจะลดค่า indegree ของจุดที่ต่อกับ
v1 ลงไปอีก 1 จะเหลือค่าในตารางดังนี้
ดังนั้นจุดต่อมาคือ v2 เมื่อเราถอด
v2 ออกไปจากกราฟ และลดค่า indegree ของจุดที่ติดกันลงไปอีก
1 จะได้ดังนี้
ดังนั้นจุดต่อมาคือ v5
เมื่อเราถอด v5 ออกไปจากกราฟ และลดค่า indegree ของจุดที่ติดกันลงไปอีก 1 จะได้ดังนี้
จุดถัดมาคือ v4 เมื่อเราถอด v4
ออกจากกราฟจะได้ค่าในตารางเป็นดังนี้
จุดถัดมาคือ v3 เมื่อถอด v3 ออกจากกราฟจะเหลือค่าในตารางดังนี้
จุดถัดมาคือ v7 เมื่อถอด v7
ออกจากกราฟจะเหลือค่าในตารางดังนี้
เมื่อครบทุกจุด ค่า indegree ของทุกจุดจะกลายเป็น 0 และลำดับของการ Dequeue
จะเป็นคำตอบของ Topological Sort ดังนี้
Shortest Path First
เป็นวิธีการค้นหาระยะทางที่สั้นที่สุดจากจุดหนึ่งไปยังจุดทุกจุดในกราฟ
โดยแบ่งออกเป็น 2 แบบ คือ แบบ Unweighted และแบบ Weighted ถ้าเป็นแบบ Unweighted จะกำหนดให้เส้นแต่ละเส้นมี Cost = 1 ดังนี้
ภาพด้านซ้ายเป็นแบบ Unweighted เราจึงกำหนดให้แต่ละเส้นทางมีน้ำหนักเป็น 1
ส่วนภาพด้านขวาเป็นแบบ Weighted และมีน้ำหนักกำหนดมาให้ในแต่ละเส้นอยู่แล้ว
วิธีการของ Shortest Path First ในกรณี Unweighted จะทำโดยกำหนดให้จุดเริ่มต้นมีระยะทางเป็น
0 และเดินจากจุดเริ่มต้นไปที่จุดที่ติดกัน และนับระยะทางเพิ่มขึ้นเรื่อยๆทีละ
1 หากมีการย้อนรอยมาถึงจุดที่เคยเดินผ่านไปแล้วจะไม่นับ
ตัวอย่างเช่น ในกรณีนี้หากให้เริ่มต้นจากจุด v1 เราจะได้ระยะทางที่
v1 = 0 ดังนี้
จาก v1 เราสามารถเดินไปที่ v2,
v3 และ v4 ได้ ให้เดินต่อไปและนับระยะทางที่ v2,
v3, v4 ขึ้นอีก 1 จาก 1 จึงกลายเป็น
2
ปัจจุบันเราอยู่ที่ v2, v3, v4 เพราะฉะนั้นเราจะต้องเดินต่อจากจุด v2 หรือ v3
หรือ v4 สมมุติเราเดินจาก v2 ต่อไปอีก 1 เส้น จะได้ภาพเป็นดังนี้
ปัจจุบันจะค้างอยู่ที่จุด v3, v4 และ v5 สมมุติว่าไล่ไปตามลำดับ เราจะต่อกันที่จุด v3
โดย v3 จะเดินไปถึง v6 ได้ดังภาพนี้
ปัจจุบันจะค้างอยู่ที่จุด v4, v5, v6 โดยเราจะเดินต่อจากจุด v4 ซึ่งสามารถไปได้ 3 ทางคือ v3, v6, v7 แต่ถ้าเดินไปที่ v3 หรือ v6 จะไม่นับเพิ่มแล้วเพราะ v3 กับ v6 เคยเดินไปถึงแล้ว ส่วน v7 จะนับเพิ่มจาก 1 เป็น 2
เมื่อมาถึงจุดนี้เราจะเหลือโหนด v5, v6, v7
ซึ่งถ้าเดินจาก v5 ไป v4 และ v7 จะเดินไม่ได้ เพราะ v4 กับ
v7 เคยเดินผ่านไปแล้ว และถ้าไปเริ่มจุด v6 ต่อ จุด v6 ไม่มีเส้นออกไปข้างนอกทำให้เดินไปไหนไม่ได้
เราจึงไปที่จุดสุดท้ายคือ v7 โดย v7 สามารถเดินไปที่
v6 ได้ แต่ v6 เคยเดินผ่านไปแล้ว
ดังนั้นจึงจบกระบวนการ Shortest Path First และได้ระยะทางที่สั้นสุดจากจุด
v1 ไปที่จุดต่างๆในกราฟได้ดังนี้
หากจะเขียนโปรแกรมเพื่อค้นหาคำตอบของ Shortest
Path First เราสามารถเขียนได้ 2 วิธี คือ
o วิธีไม่ใช้ Queue แต่กำหนดสถานะของจุดแต่ละจุดว่าจุดไหนเดินไปแล้วหรือไม่
(เรียกสถานะนี้ว่า Known)
o วิธีใช้ Queue เราไม่จำเป็นต้องมีสถานะ Known
ของแต่ละจุด
วิธีไม่ใช้ Queue เพื่อหา Shortest Path First
วิธีไม่ใช้ Queue ตารางที่ใช้เก็บตัวแปรจะมีค่าดังนี้
สมมุติว่าเราเริ่มต้นที่จุด v1 เพราะฉะนั้น distance ของ v1 จะเป็น
0 ดังนี้
และถ้าเราเดินจากจุด v1 ไปที่
v2, v3, v4 จะมีค่าในตารางดังนี้
และถ้าเราเดินจากจุด v2 ไปที่
v5 จะมีค่าในตารางดังนี้
และถ้าเราเดินต่อจากจุด v3 ไปที่
v6 จะมีค่าในตารางดังนี้
และสุดท้ายเมื่อเราเดินต่อจากจุด v4 ไปที่ v7 จะได้ค่าในตารางดังนี้
วิธีใช้ Queue เพื่อหา Shortest Path First
วิธีที่ใช้ Queue ตารางที่ใช้เก็บตัวแปรจะมีลักษณะดังนี้
สมมุติว่าถ้าเราจะเริ่มจากจุด v3 ดังนั้นเราจะนำจุด v3 ไปเข้าคิวรอไว้ก่อน และ distance
ของ v3 จะเป็น 0 ดังนี้
ในแต่ละรอบเราจะดึงจุดถัดไปจากคิว (เรียกว่า Dequeue)
และหาดูว่าจุดนั้นต่ออยู่กับจุดไหน
เราจะเดินไปที่ทุกจุดที่ต่ออยู่กับจุดนั้นและนับค่า distance ในแต่ละจุดที่เดินไปถึงเพิ่มขึ้นอีก 1 รวมทั้งให้สถานะ
known เป็น T ด้วย
สุดท้ายเราจะนำจุดเหล่านั้นมาเข้าคิวรอไว้เพื่อนับให้เป็นจุดถัดไป
เพราะฉะนั้นรอบถัดไปเราจะทำเช่นเดียวกันคือดึง v1
ออกจากคิว จุดที่ต่อไปจาก v1 คือ v2 และ v4 เราจะเพิ่มระยะทางที่ v2 และ v4 เป็น 2 และนำ v2,
v4 ไปเข้าคิวต่อดังนี้
ถัดมาคือ v6 ซึ่ง v6 ไม่มีจุดต่อเนื่องไปที่ไหนเลย v6 จึงแค่ถูก
Dequeue และทิ้งไป ดังนี้
ถัดมาคือ v2 เมื่อเราดึง v2
ออกจากคิว จะพบว่า v2 สามารถเดินต่อไปที่จุด v4
และ v5 แต่ v4 มีสถานะ known
เป็น T แล้วดังนั้นเราจะไม่ยุ่งกับ v4 จึงเหลือแต่ v5 เท่านั้น เราจึงกำหนด distance
ของ v5 เป็น 3 และได้ค่าในตารางกับ
Queue เป็นดังนี้
ถัดมาคือ v4 เมื่อเราดึง v4
ออกมาจากคิว จะพบว่าเราสามารถเดินต่อไปได้ที่จุด v3, v6 และ v7 แต่เนื่องจาก v3 กับ v6
มีสถานะ known เป็น T ไปแล้ว
ดังนั้นจะเหลือเพียงจุดเดียวที่เราจะกำหนด distance ให้คือ v7
ค่าในตารางจะเป็นดังนี้
แม้ว่าเราจะได้ distance ครบทุกจุดแล้วก็ตาม
แต่ยังเหลือจุด v5 และ v7 อยู่ในคิว
เมื่อเราดึง v5 ออกจากคิว
และทำต่อจะพบว่าไม่มีค่าเปลี่ยนแปลง แม้ว่า v5 จะสามารถเดินไปที่
v4 และ v7 ได้ แต่ทั้ง v4 กับ v7 ต่างก็มีสถานะเป็น known ไปเรียบร้อยแล้ว
และสุดท้ายเราดึง v7 ออกมาจากคิว
และจะเดินต่อจาก v7 ไปที่ v6 แต่
v6 มีสถานะ known เป็น T ไปแล้ว จึงครบทุกจุดในกราฟ และคิวว่างเปล่า ดังนี้
จากตาราง Shortest Path First ที่เราเก็บผลลัพธ์มาได้ บอกให้เรารู้ว่า ถ้าเราจะเริ่มเดินจากจุด v3
ไปที่ v7 จะต้องใช้ระยะทางที่สั้นที่สุดคือ 3
โดยเดินไปตามเส้นทาง v3, v1, v4, v7 ดังนี้
9.3.2 Dijkstra’s Algorithm
(อ่านว่า ได้ตร้า อัลกอริธึม) ใช้สำหรับ
Weighted Graph แต่หลักการคล้ายกับ Unweighted Shortest Path
First ที่เราทดลองผ่านมาแล้ว คือระหว่างที่เดินไปที่จุดถัดไป
ก็ให้บวกทดระยะทางเพิ่มขึ้น โดยนำค่าน้ำหนักของเส้นทางที่เดินไปมาบวกเพิ่มกับระยะทางปัจจุบัน
เราสามารถแสดงวิธีการ Dijkstra ได้ดังนี้
การกำหนดค่าเริ่มต้น จะให้สถานะ known ของทุกจุดเป็น F และระยะทางเป็น INFINITY สมมุติกราฟที่เราจะใช้เป็น Unweighted Graph ดังภาพด้านซ้าย
สมมุติว่าจุดเริ่มต้นที่เราจะเริ่มเดินคือจุด v1
ดังนั้นเราจะกำหนดให้ distance ที่ v1 เป็น 0 แต่ known ยังมีค่าเป็น
F อยู่ดังนี้
ในรอบที่ 1 ของการทำงาน Dijkstra
จะค้นหาจุดที่มี distance น้อยที่สุด
และมีสถานะ known เป็น F ดังนี้
ต่อจากนั้นเปลี่ยน known จาก
F เป็น T ดังนี้
และคำนวณค่าระยะทางไปที่จุด v2 และ v4 และนำค่าไปใส่ดังนี้
จะถือว่า Dijkstra เสร็จไป 1
รอบ หลังจากนั้นจะขึ้นรอบที่ 2 โดยทำเช่นเดียวกัน
ดังนี้
และจุดที่เดินจาก v4 ไปถึงได้คือ
v3, v5, v6 และ v7 เราจะคำนวณระยะทางและนำค่าไปใส่ไว้ให้
เมื่อขึ้นรอบที่ 3 ตัวที่ถูกเลือกมาทำก่อนคือจุด
v2 เนื่องจากมีสถานะเป็น F และ distance
2 เป็นค่าน้อยสุด
และจุดที่เดินต่อจากจุด v2 ไปคือ
v5 กับ v4 แต่เนื่องจาก v4 มีสถานะ known เป็น T แล้ว
ดังนั้นเราจึงจะคำนวณ distance เฉพาะของ v5 เท่านั้น ดังนี้
เสร็จรอบที่ 3 Dijkstra จะได้ค่าระยะทางดังนี้
เมื่อขึ้นรอบที่ 4 จะค้นหาจุดที่เป็น
F และมีค่า distance น้อยที่สุดนั่นก็คือจุด
v3 และ v5 สมมุติว่าเริ่มที่ v3
ก่อนจะได้ภาพดังนี้
จุดเดินจาก v3 ไปถึงได้คือ v1
และ v6 ในที่นี้ v1 มีสถานะ
known เป็น T ไปแล้ว
ดังนั้นจึงเหลือแต่ v6 ที่เราต้องคำนวณค่า distance และค่า distance ที่คำนวณใหม่คือ 8 มีค่าน้อยกว่า 9 ดังนั้นเราจะปรับค่าของ v6 ใหม่ได้ดังนี้
เมื่อจบรอบที่ 4 Dijkstra จะมีระยะทางดังนี้
เมื่อขึ้นรอบที่ 5 จุดที่มีสถานะ
known เป็น F และมีค่า distance
น้อยที่สุดคือ v5 เราจะเริ่มทำต่อดังนี้
จุดที่ v5 เดินไปถึงคือ v7
และเมื่อคำนวณระยะทางใหม่คือ 3 + 6 = 9 แต่เนื่องจาก
9 > 5 ดังนั้นที่ v7 เราไม่จำเป็นต้องปรับค่าระยะทาง
จะได้ผลลัพธ์เมื่อจบรอบที่ 5 ดังนี้
เมื่อขึ้นรอบที่ 6 จุดที่มีสถานะ
known เป็น F และมีค่าน้อยที่สุดคือ v7
ดังนั้นเราจะเริ่มคำนวณที่ v7 ดังนี้
จุดที่เดินต่อจาก v7 ไปคือจุด
v6 เราคำนวณระยะทางใหม่ได้เป็น 5 + 1 = 6 และเนื่องจาก 6 < 8 ดังนั้นเราจำเป็นต้องปรับค่าระยะทางที่
v6 ใหม่ให้เป็น 6 ดังนี้
และเมื่อจบรอบที่ 6 Dijkstra จะมีค่าระยะทางเก็บอยู่ดังนี้
รอบที่ 7 รอบสุดท้ายนี้จะเหลือตัวที่มีสถานะ
known เป็น F และ distance น้อยที่สุดอยู่ตัวเดียวคือ v6 และเนื่องจาก v6
ไม่มีจุดเดินต่อไปที่ไหนอีก (ถึงมีจุดเดินต่อไป
แต่ทุกตัวที่เหลือเป็น T ไปหมดแล้วก็ไม่มีการคำนวณใหม่อยู่ดี)
ดังนั้นเมื่อจบรอบที่ 7 จะมีค่าระยะทางเก็บอยู่ดังนี้
ความคิดเห็น
แสดงความคิดเห็น