CoE KKU

ในหัวข้อนี้จะกล่าวถึงปัญหาที่เรียกว่า shortest-path problems อินพุตเป็น weighted graph: กล่าวคือ edge $(v_i, v_j)$ มีค่าใช้จ่าย (cost) $c_{i,j}$ ในการท่องผ่าน edge ไป ค่าใช้จ่ายของเส้นทาง $v_1,v_2, ... v_n$ คือ $∑_{i=1}^{N-1}c_{i,i+1}$ เรียกว่า weighted path length ส่วน unweighted path length ก็คือ จำนวน edges บนเส้นทางนั้นซึ่งก็คือ N – 1

SINGLE-SOURCE SHORTEST-PATH PROBLEM:

ให้อินพุตเป็น weighted graph, $G = (V, E)$, และถ้ามี vertex s หนึ่ง vertex ให้ทำการหา shortest weighted path จาก s ไปยัง vertex อื่น ๆ ทุก vertex ใน $G$

เช่น กราฟในรูปที่ 9.8 มี shortest weighted path จาก v1 ถึง v6 มี cost คือ 6 ตามเส้นทางจาก v1 ไป v4 ไป v7 ไป v6 และมี shortest unweighted path ระหว่าง vertex ทั้งสองคือ 2 โดยทั่วไปแล้วถ้าไม่ได้ระบุว่าเป็นกราฟชนิดใดก็หมายถึงตามที่ปรากฏในกราฟกล่าวคือถ้าเส้นทางมี weight กำกับอยู่ก็จะหมายถึง weighted graph และจะเห็นว่ากราฟในรูปที่ 9.8 ไม่มีเส้นทางจาก v6 ถึง v1

กราฟในรูปที่ 9.8 ไม่มี edge ที่มีค่า cost เป็นค่าติดลบ กราฟในรูปที่ 9.9 แสดงปัญหาที่เกิดขึ้นได้จากการมี negative edges เส้นทางจาก v5 ไป v4 มี cost = 1 แต่มีเส้นทางที่สั้นกว่านั้น คือเส้นทางตามการวนรอบ (loop) v5, v4, v2, v5, v4 ซึ่งมี cost = -5 ความจริงนี่ยังไม่ใช่เส้นทางที่สั้นที่สุดเนื่องจากเราสามารถเดินวนรอบไปได้เรื่อย ๆ นั่นเอง และทำนองเดียวกับเส้นทางที่สั้นที่สุดจาก v1 ไป v6 เนื่องจากเราจะเข้าสู่การวนรอบเดียวกัน นี่กล่าวได้ว่าเส้นทางที่สั้นที่สุดระหว่าง 2 จุดนี้ไม่มีนั่นเอง การวนรอบดังกล่าวนี้เรียกว่า negative-cost cycle ซึ่งเมื่อเกิดขึ้นในกราฟแล้วก็ไม่สามารถหาเส้นทางที่สั้นที่สุดได้ อย่างไรก็ตามการมี edge ที่เป็น Negative-cost edges ไม่ใช่สิ่งที่เสียหายเหมือนกับการมี cycles ในกราฟ เพียงแต่มันจะทำให้การแก้ปัญหายุ่งยากมากขึ้น เพื่อความสะดวกเราจะกำหนดให้เส้นทางที่สั้นที่สุดจาก vertex s ไป s (คือตัวมันเอง) มีค่าเป็น 0

มีปัญหาหลายอย่างที่เราอาจจะต้องแก้ด้วยการแก้ปัญหา shortest-path problems เช่น ถ้าให้ vertex เป็นเครื่องคอมพิวเตอร์และมี edge เป็นเส้นเชื่อมต่อระหว่างคอมพิวเตอร์และ cost แทนค่าใช้จ่ายในการสื่อสาร ดังนั้นเราก็จะสามารถใช้อัลกอริทึมของการหา shortest-path เพื่อหาวิธีที่ต้องจ่ายน้อยที่สุดในการสื่อสารระหว่างคอมพิวเตอร์

เราอาจจะจำลองเส้นทางการบินของสายการบินหรือขนส่งมวลชนอื่น ๆ ได้ด้วยกราฟและใช้อัลกอริทึมของการหา shortest-path เพื่อหาวิธีที่ดีสุดระหว่าง 2 จุด ในการประยุกต์ใช้งานดังกล่าวนี้หรือกับปัญหาอื่น ๆ ทำให้เราต้องค้นหาเส้นทางที่สั้นที่สุดที่ใช้เดินทางจาก vertex หนึ่ง (เช่น s) ไปยังอีก vertex หนึ่ง (เช่น t) อย่างไรก็ตามในขณะนี้ ยังไม่มีอัลกอริทึมที่ใช้ค้นหาเส้นทางจาก s ไปยังอีก vertex หนึ่งที่สามารถทำงานได้เร็วกว่าอัลกอริทึมที่ใช้ค้นหาเส้นทางจาก s ไปยัง vertex อื่น ๆ ทุก ๆ vertex ในกราฟนั้น

เราจะกล่าวถึงอัลกอริทึมที่ใช้แก้ปัญหานี้ 4 วิธี ในตอนแรกจะกล่าวถึงปัญหา unweighted shortest-path และแก้โดยใช้เวลาเป็น $O(|E| + |V|)$ จากนั้นแสดงการแก้ปัญหา weighted shortest-path โดยสมมติให้กราฟไม่มี negative edges และมี running time เป็น $O(|E|\ log\ |V|)$ เมื่อใช้โครงสร้างข้อมูลเหมาะสม กรณีที่กราฟมี negative edges จะได้เสนอมีวิธีแก้ปัญหาอย่างง่ายแต่จะต้องใช้เวลาเป็น $O(|E|\ ×\ |V|)$ สุดท้ายแก้ปัญหา weighted graph ที่เป็น acyclic graphs แบบพิเศษด้วยเวลาที่เป็น linear

รูปที่ 9.10 แสดง unweighted graph, G. เริ่มต้นจาก vertex, s, ใด ๆ เราจะทำการหาเส้นทางที่สั้นที่สุดจาก s ไปยัง vertices อื่น ๆ ทั้งหมด โดยที่ในเวลานี้เราไม่สนใจว่าจะมีเส้นทางใดบ้าง เราเพียงต้องการความยาวของเส้นทางที่สั้นที่สุดเท่านั้นซึ่งในที่นี้ก็คือจำนวน edge ในเส้นทางนั้นเนื่องจากเป็นกราฟที่ edge ไม่มี cost (คือ cost = 1) เส้นทางที่ใช้เพื่อให้ได้ค่า cost จะได้จากการบันทึกเพิ่มเติมเท่านั้น

สมมุติเลือก s ให้เป็น v3 นั่นคือเส้นทางที่สั้นที่สุดจาก s ไป v3 มีค่าความยาวเป็น 0 เราจะทำการบันทึกค่านี้ลงในกราฟดังแสดงในรูปที่ 9.11

จากนี้เราจะต้องค้นหา vertices ทั้งหมดที่มีระยะทาง 1 หน่วยจาก s ซึ่งก็คือ vertices ที่เป็น adjacent vertex ของ s นั่นเอง และจะพบว่า v1 และ v6 มีระยะทาง 1 หน่วยจาก s ดังแสดงในรูปที่ 9.12

ต่อไปเป็นการหา vertices ที่มีระยะทางที่สั้นที่สุดจาก s ซึ่งก็คือที่มีระยะ 2 หน่วยจาก s นั่นเอง และทำได้ด้วยการค้นหา adjacent vertices ของ v1 และ v6 และต้องเป็น vertices ที่ยังไม่เคยเข้าถึง (unknown) ซึ่งก็จะพบว่า v2 และ v4 คือ vertices ที่ต้องการ รูปที่ 9.13 แสดงผลที่ได้

สุดท้ายเป็นการหา adjacent vertices ของ v2 และ V4 และพบกับ v5 และ v7 ที่มีระยะทางที่สั้นที่สุดจาก s ซึ่งก็คือที่มีระยะ 3 หน่วย ดังรูปที่ 9.14 เป็นอันครบทุก vertices

วิธีการค้นหา vertices ในกราฟที่ได้กล่าวมานั้นเป็นกรรมวิธีที่เรียกว่า breadth-first search วิธีการแบบนี้จะประมวลผล vertices เป็นชั้น ๆ (layers) กล่าวคือ vertices ที่อยู่ใกล้กับจุดเริ่มต้นจะได้รับการทำงานก่อนจนครบทุก vertex และ vertices ที่อยู่ห่างที่สุดจะได้รับการทำงานสุดท้าย การทำงานแบบนี้มีลักษณะเดียวกับการท่องไปในทรีด้วยรูปแบบ level traversal

รูปที่ 9.15 แสดงตารางเริ่มต้นของอัลกอริทึมที่จะใช้ในการบันทึกความก้าวหน้าในการทำงาน โดยเราจะบันทึกข้อมูล 3 อย่างสำหรับแต่ละ vertex คือ ข้อมูลอย่างแรกคือระยะทางจาก s ด้วยการเก็บค่าไว้ใน dv และในตอนเริ่มต้นทุก vertices ไม่สามารถเดินทางไปถึงจาก s ได้ ยกเว้นตัว s เอง (ซึ่งก็จะมีความยาวระยะทางเป็น 0) ข้อมูลอย่างที่ 2 คือรายการใน pv เป็น bookkeeping variable ซึ่งทำให้เราพิมพ์เส้นทางที่ใช้จริงในการเดินทางจาก s ไป vertex v ได้ และข้อมูลอย่างที่ 3 คือรายการ known ซึ่งจะถูกตั้งค่าให้เป็น true หลังจากที่ vertex นั้นผ่านการประมวลผลแล้ว ในสภาวะเริ่มต้นรายการนี้ทุกตัวมีค่านี้เป็น unknown รวมทั้ง vertex เริ่มต้นด้วย เมื่อ vertex ถูกตั้งค่าเป็น known แล้วก็ประกันได้ว่าจะไม่มีเส้นทางจาก s ที่สั้นกว่านี้อีกแล้วและดังนั้นการประมวลผล vertex ดังกล่าวนี้เป็นอันสิ้นสุด

อัลกอริทึมพื้นฐานที่ใช้นี้แสดงในรูปที่ 9.16 ซึ่งจำลองตารางรูปที่ 9.15 ด้วยการประกาศให้ vertices มีค่า known ที่มีระยะ d = 0 ตามด้วยที่ d = 1 ตามด้วย d = 2 ไปเรื่อย ๆ และตั้งค่าให้ adjacent vertices w ทั้งหมดที่ยังคงมีค่าของระยะ dw = ∞ ไปเป็นค่าระยะ dw = d + 1

รูปที่ 9.15 สถานะเริ่มต้นของตารางที่ใช้ในการหา unweighted shortest-path

เราสามารถพิมพ์เส้นทางจริงที่ใช้ในการเดินทางจาก s ไปยัง vertices ต่าง ๆ ได้ด้วยการเดินทางย้อนกลับผ่านทางตัวแปร pv ซึ่งจะกล่าวถึงอีกครั้งเมื่อกล่าวถึงกรณีกราฟแบบ weighted graph

running time ของอัลกอริทึมคือ $O(|V|^2)$ เพราะมี nested for loops ส่วนที่ทำให้ประสิทธิภาพการทำงานไม่ดีคือลูปด้านนอกยังคงต้องทำวนรอบจนกระทั่งถึง NUM_VERTICES -1 ถึงแม้ว่า vertices ทั้งหมดจะถูกเปลี่ยนเป็น known ตั้งแต่แรก ๆ แล้วก็ตาม

ถึงจะใช้การทดสอบพิเศษเพื่อหลีกเลี่ยงสิ่งที่กล่าวมานั้นก็ไม่ช่วยให้ worst-case running time ดีขึ้นกรณีที่สภาวะของอินพุตเป็นไปดังแสดงในรูปที่ 9.17 เมื่อเริ่มต้นที่ vertex v9

เราสามารถเพิ่มประสิทธิภาพได้ด้วยวิธีเดียวกับที่ใช้ใน topological sort โดยที่ ณ เวลาหนึ่งจะมี vetices ที่เป็น unknown ที่มี dv ≠ ∞ อยู่สองประเภทคือ มีบางตัวมี dv = currDist และบางตัวมี dv = currDist + 1 ดังนั้นจึงเป็นการเสียเวลาโดยเปล่าประโยชน์ที่จะค้นหาในตารางไปทั้งหมดเพื่อหา vertex ที่ต้องการตามคำสั่งบรรทัดที่ 2 และ 3

       void unweighted ( Vertex s ) 
       {	vertex v, w;
/*1*/      	s.dist = 0;
/*2*/	for ( int currDist = 0; currDist < NUM_VERTICES; currDist++)
/*3*/       for each vertex v
/*4*/          if ( ( !v.known ) && ( v.dist == currDist ) )
	           {
/*5*/             v.known = true;
/*6*/             for each w adjacent to v
/*7*/                 if ( w.dist = INTFINITY )   {
/*8*/                    	w.dist = currDist + 1;
/*9*/                     	w.path = v;
		               }
	           }
      }

รูปที่ 9.16 Pseudocode สำหรับ unweighted shortest-path algorithm

เราสามารถปรับปรุงประสิทธิภาพการทำงานดังกล่าวได้โดยใช้โครงสร้าง queue เข้าช่วยเพียงตัวเดียว ดังนี้ ณ จุดเริ่มต้นรอบการทำงานนั้นภายใน queue มีเฉพาะ vertices ที่มีระยะทางเป็น currDist (ค่าของ currDist เริ่มต้นด้วย 0) เมื่อเราเพิ่ม adjacent vertices ที่มีระยะ currDist + 1 ด้วยการ enqueue ทางด้านท้าย queue เราก็จะสามารถประกันได้ว่ามันจะไม่ได้รับการประมวลผลจนกว่า vertices ทั้งหมดที่มีระยะเป็น currDist จะได้รับการประมวลผลเสร็จสิ้นเสียก่อน นั่นคือหลังจากที่ vertices ที่มีระยะ currDist ตัวสุดท้ายที่อยู่ใน queue ได้รับการประมวลผลแล้วก็จะเหลือเฉพาะ vertices ที่มีค่าระยะเป็น currDist + 1 เท่านั้นที่เหลืออยู่ใน queue และจะเริ่มการทำงานแบบเดิมต่อไป

อัลกอริทึมใหม่ที่กล่าวข้างบนแสดงในรูปที่ 9.18 ใน pseudocode เรากำหนดให้ vertex เริ่มต้นคือ s ใช้เป็นพารามิเตอร์ส่งเข้าในโปรแกรม และเป็นไปได้ที่ queue อาจจะว่างลงก่อนโดยที่มีบาง vertices ยังไม่ได้เข้าถึงจาก vertex เริ่มต้น และ vertex เหล่านั้นก็จะถูกกำหนดระยะของ vertices เหล่านั้นให้เป็น INFINITY สำหรับอัลกอริทึมนี้ไม่จำเป็นต้องใช้ฟิลด์ known อีกต่อไป เนื่องจากว่าเมื่อ vertex ที่ได้รับการประมวลผลแล้วจะไม่กลับเข้าไปใน queue อีกต่อไป รูปที่ 9.19 แสดงค่าต่าง ๆ ที่เปลี่ยนไปในกราฟในระหว่างการทำงานของอัลกอริทึม ฟิลด์ known ยังคงอยู่ก็เพื่อให้การติดตามการเปลี่ยนแปลงของตารางง่ายขึ้นเท่านั้น

ด้วยการใช้การวิเคราะห์เช่นเดียวกับที่ใช้ใน topological sort จะได้อัลกอริทึมเป็น O(|E| + |V|), เมื่อใช้ adjacency lists

void unweighted ( Vertex s ) 
{	
	    Queue q;
		vertex v, w;
/*1*/	q = new Queue();
/*2*/   q.enqueue( s );	s.dist = 0;
/*3*/	while ( !q.isEmpty() ) 
	    {
/*4*/       v = q.dequeue;
/*5*/       v.known = true;		// Not really needed anymore
/*6*/       for each w adjacent to v
/*7*/          if ( w.dist = INTFINITY )
	           {
/*8*/               w.dist = v.dist + 1;
/*9*/               w.path = v;
/*10*/	            q.enqueue( w );
	            }
	    }
} 

รูปที่ 9.18 Pseudocode ของ unweighted shortest-path algorithm  

รูปที่ 9.19 แสดงการเปลี่ยนแปลงค่าระหว่างการทำงานของอัลกอริทึม unweight shortest-path

กรณีที่กราฟเป็น weighted graph การแก้ปัญหาก็จะยากขึ้น อย่างไรก็ตามเรายังก็ยังคงใช้แนวคิดเดียวกับ unweighted graph

ข้อมูลต่าง ๆ ที่เราจะใช้ยังคงเหมือนเดิม กล่าวคือแต่ละ vertex ถูกกำหนดเป็น known หรือ unknown เก็บค่าระยะ dv ของแต่ละ vertex เช่นเดิมและระยะทางนี้จะเป็นระยะทางที่สั้นที่สุดจาก s ไป v โดยเดินทางผ่านเส้นทางที่จะใช้เฉพาะ vertices ต่าง ๆ ที่เป็น known เท่านั้น และเช่นเดียวกับที่ผ่านมา เราจะบันทึกค่า pv, ซึ่งเป็น vertex สุดท้ายที่ทำให้เกิดการเปลี่ยนแปลงขึ้นกับ dv ของ vertex นั้น ๆ

วิธีการที่ใช้ในการแก้ปัญหา single-source shortest-path คือ Dijkstra's algorithm ซึ่งเป็นอัลกอริทึมหนึ่งที่เป็น greedy algorithm ซึ่ง greedy algorithms เป็นการแก้ปัญหาเป็น stages โดยใช้สิ่งที่ดูเหมือนว่าดีที่สุดในแต่ละ stage ปัญหาใหญ่ของ greedy algorithms คือบางสถานการณ์มันก็แก้ปัญหาไม่ได้

Dijkstra's algorithm ทำงานเป็น stages เช่นเดียวกับ unweighted shortest-path algorithm ในแต่ละ stage ของการทำงานจะทำการเลือก vertex v ตัวหนึ่งที่มีค่า dv น้อยที่สุดในบรรดา unknown vertices และประกาศให้เป็นเส้นทางที่สั้นที่สุดจาก s ไป v (กำหนดให้มันเป็น known) งานที่เหลือใน stage คือการปรับปรุงค่าของ dw

ในกรณี unweighted เราตั้งค่าให้ dw = dv + 1 ถ้า dw = ∞ นั่นคือเราลดค่าของ dw ลงถ้าหากว่า vertex v เป็นตัวที่ทำให้ได้เส้นทางที่สั้นกว่า ถ้าเราใช้วิธีเดียวกันนี้กับกรณี weighted graph เราก็จะกำหนดให้ dw = dv + cv,w ถ้าค่าใหม่นี้ทำให้ dw ดีขึ้น กล่าวอีกอย่างก็คือ อัลกอริทึมจะตัดสินใจว่าจะเลือกใช้ v ในเส้นทางเดินไปหา w หรือไม่ โดยที่มีค่าใช้จ่ายเดิมคือ dw ซึ่งเป็นค่าใช้จ่ายที่ไม่รวมค่าใช้จ่ายที่เกิดขึ้นจากการใช้ v ดังนั้น ค่าใช้จ่ายที่คำนวณข้างบนนั้นคือค่าใช้จ่ายที่ถูกที่สุดในการใช้เส้นทางที่รวม v และ vertices อื่น ๆ ที่เป็น known เท่านั้น พิจารณากราฟในรูปที่ 9.20 และมีรูปที่ 9.21 เป็นค่าสภาวะเริ่มต้นของกราฟโดยให้ vertex เริ่มต้น s คือ v1 และมีความยาวของเส้นทางเป็น 0 และกำหนดให้ vertex นี้เป็น known หลังจากเมื่อ v1 ถูกเปลี่ยนเป็น known แล้วก็จะต้องมีการปรับเปลี่ยนรายการบางรายการ vertices ที่เป็น adjacent กับ v1 คือ v2 และ v4 ซึ่งรายการของทั้งสอง vertices ต้องปรับเปลี่ยนดังในรูปที่ 9.22

ต่อจากนั้นเลือก v4 และตั้งค่าเป็น known และมี vertices v3, v5, v6 และ v7 เป็น adjacent vertices และจะต้องทำการปรับเปลี่ยนดังแสดงในรูปที่ 9.23 จากนั้นเลือก v2 และพบว่า v4 เป็น adjacent vertex แต่เป็น known แล้วจึงไม่ปรับเปลี่ยน และ v5 ก็เป็น adjacent แต่ไม่มีการปรับเปลี่ยนใด ๆ เนื่องจากระยะทางที่ผ่านมาทาง v2 คือ 2 + 10 = 12 แต่ได้รับรู้ระยะเท่ากับ 3 ไปแล้ว ดูรูปที่ 9.24 แสดงสภาวะหลัง vertices เหล่านี้ถูกเลือก

ต่อไปเลือก v5 มีระยะ 3 และมี v7 เป็น adjacent แต่ไม่ปรับเปลี่ยนเพราะว่า 3 + 6 > 5 จากนั้นเลือก v3 และปรับเปลี่ยนระยะสำหรับ v6 ลงเป็น 3 + 5 = 8 ผลแสดงดังรูปที่ 9.25 ต่อไปเลือก v7 ซึ่งต้องปรับเปลี่ยน v6 เป็น 5+1 = 6 ดังรูปที่ 9.26 สุดท้ายเลือก v6 และรูปที่ 9.27 แสดงผลการทำงาน

รูปที่ 9.27 หลัง v6 ได้รับการตั้งค่าเป็น known และเสร็จสิ้นการทำงาน

ในการแสดงเส้นทางที่ใช้จาก vertex เริ่มต้นไปยัง vertex v ใด ๆ เราสามารถใช้ฟังก์ชันแบบ recursive เพื่อติดตามเส้นทางที่ปรากฏอยู่ในตัวแปร p ได้

รูปที่ 9.29 แสดง pseudocode ของ Dijkstra's algorithm โดยในแต่ละ Vertex จะมีการจัดเก็บข้อมูลในฟิลด์ต่าง ๆ ที่จะใช้ในอัลกอริทึม เราสมมติให้สามารถอ่านกราฟเข้ามาในอะเรย์ของ Vertex ได้พร้อมด้วยการสร้าง adjacency lists ด้วยฟังก์ชัน readGraph หลังจากนั้นก็จะเป็นการกำหนดค่าเริ่มต้นของฟิลด์ต่าง ๆ ด้วยฟังก์ชันดังรูปที่ 9.30

การแสดง (พิมพ์) เส้นทางที่ใช้ที่ได้จากการทำงานของอัลกอริทึมทำได้ด้วย recursive routine ในรูปที่ 9.31 รูปที่ 9.32 แสดงอัลกอริทึมหลักที่ใช้ทำงานซึ่งเป็นเพียงการเติมข้อมูลลงในตารางที่เตรียมมาแล้วด้วย greedy selection เท่านั้น

รูปที่ 9.28 สถานะแต่ละขั้นตอนของกราฟเมื่อใช้อัลกอริทึมของ Dijkstra

class Vertex
{
	public	List 		adj;    		// Adjacent vertices
	public 	boolean		known;
	public 	DistType	dist;   		// DistType is probably int 
	public	Vertex     	path;   
	//	Other fields and methods as needed
}

รูปที่ 9.29 Declarations ของ Dijkstra's algorithm

public Vertex createTable( )
{
/*1*/  Vertex [ ] t = readGraph(  );      // read graph somehow 
/*2*/  for ( int i = 0; i < t.length; i++ )
	   {
/*3*/      t[ i ].known = false;
/*4*/      t[ i ].dist = INFINTY;
/*5*/      t[ i ].path = null;
	    }
/*6*/   NUM_VERTICES = t.length;
}

รูปที่ 9.30 routine ที่ให้ค่ากลับเป็นอะเรย์ของ Vertex

/* print shortest path to v after dijkstra has run, assume that the path exists */
void printPath ( Vertex v )
{	if ( v.path != null )
	{   printPath( v.path );
	    System.out.print ( " to " );
	}
	System.out.print ( v ); 
 }
 

รูปที่ 9.31 Routine เพื่อพิมพ์เส้นทาง shortest path

การพิสูจน์ด้วยวิธี contradiction จะแสดงให้เห็นว่าอัลกอริทึมนี้ใช้งานได้เสมอตราบเท่าที่ไม่มี negative cost edge ถ้ามี edge ที่เป็น negative cost อัลกอริทึมอาจให้คำตอบผิดได้ running time ขึ้นอยู่กับว่าเราจะทำอย่างไรกับ vertices ถ้าหากอัลกอริทึมที่ใช้เป็นการไล่ตรวจค่า (scan) ไปตามตารางเพื่อหาค่า dv ที่น้อยที่สุด เราก็จะใช้การทำงาน $O(|V|)$ หน่วยเวลาในแต่ละ phase การทำงาน ดังนั้นจะต้องใช้เวลาทั้งสิ้นเป็น $O(|V|^2)$ หน่วยเวลาเพื่อที่จะหาค่าที่น้อยที่สุดตลอดการทำงานของอัลกอริทึม เวลาที่ใช้ในการปรับเปลี่ยนค่า dw เป็นเวลาคงที่ต่อการปรับเปลี่ยนแต่ละครั้ง และต้องปรับเปลี่ยนหนึ่งครั้งต่อหนึ่ง edge เท่านั้น ดังนั้นจำนวนการปรับเปลี่ยนค่านี้ทั้งหมดจึงเป็น $O(|E|)$ รวม running time ทั้งหมดของอัลกอริทึมคือ $O(|E| + |V|^2) = O(|V|^2)$ ถ้ากราฟเป็นแบบ dense ที่มี $|E| = \Theta(|V|^2)$ แล้วอัลกอริทึมนี้ก็จะเป็น linear ในเทอมของจำนวน edges

ถ้ากราฟเป็นแบบ sparse ที่มี $|E| = \Theta(|V|)$ การทำงานจะช้ามาก ในกรณีนี้เราอาจจะจัดเก็บค่าของระยะทางไว้ในโครงสร้าง priority queue ซึ่งทำได้ 2 วิธีที่ทั้ง 2 วิธีคล้ายคลึงกัน

จากโปรแกรมรูปที่ 9.32 รวมการทำงานของบรรทัดที่ 3 และ 6 เป็นการทำงาน deleteMin เนื่องจาก vertex ที่เป็น unknown หลังจากถูกพบว่าเป็น vertex ที่มีค่าน้อยที่สุดแล้ว (คือ known แล้ว) มันจะต้องไม่ได้รับความสนใจอีกต่อไป ส่วนการปรับปรุงค่าในบรรทัดที่ 10 นั้นสามารถทำได้ 2 ทางด้วยกัน ทางหนึ่งคือใช้การทำงาน decreseKey ดังนั้น เวลาที่ต้องใช้ในการหาค่าน้อยที่สุดคือ $O(log\ |V|)$ เท่า ๆ กันกับการทำงาน decreseKey ทำให้ได้เวลาของ running time เป็น $O(|E|\ log\ |V| + |V|\ log\ |V|) = O(|E|\ log\ |V|)$ ซึ่งดีกว่าขอบเขตเวลาของ sparse graph เนื่องจากว่า priority queue ไม่สนับสนุนการทำงาน find ที่มีประสิทธิภาพ

ถ้าใช้โครงสร้างข้อมูลอื่น อาจจะทำให้ time bounds ของ Dijkstra's algorithm ดีขึ้นได้

void	dijkstra ( Vertex s )
{
	   vertex v, w;
/*1*/  s.dist = 0;  
/*2*/  for( ; ; )
	   {
/*3*/  	v = smallest unknown distance vertex;
/*4*/  	if (v == null )
/*5*/	    break;
/*6*/  	v.known = true;
/*7*/  	for each w adjacent to v
/*8*/       if ( !w.known )
/*9*/           if ( v.dist + cvw < w.dist )
	          	{   /* update w */
/*10*/              decrease( w.dist  to v.dist + cv,w );
/*11*/              w.path = v;
	          	 }
	    }
} 

รูปที่ 9.32 Pseudocode ของ Dijkstra's algorithm

อีกวิธีหนึ่งคือให้บรรจุ w และค่า dw ใหม่ลงใน priority queue ทุกครั้งที่มีการทำงานของบรรทัดที่ 10 ดังนั้นภายใน priority queue จึงอาจมีตัวแทนของ vertex หนึ่งมากกว่า 1 ตัวแทน เมื่อมีการทำงาน deleteMin เพื่อย้าย vertex ที่มีค่าที่น้อยที่สุดออกจาก priority queue นั้นจะต้องตรวจดูด้วยว่ามันไม่ได้เป็น vertex ที่เป็น known ดังนั้นการทำงานบรรทัดที่ 3 จึงต้องทำงาน deleteMin วนรอบจนกระทั่งพบกับ vertex ที่เป็น unknown ขนาดของ priority queue อาจจะมีขนาดใหญ่ได้ถึง $|E|$ อย่างไรก็ตามมันก็ไม่มีผลกระทบต่อขอบเขตเวลา (asymptotic time bound) เนื่องจากว่า $|E| ≤ |V|^2$ โดยนัยก็หมายความว่า $log |E| ≤ 2\ log |V|$ ดังนั้นเราก็ยังคงได้อัลกอริทึมที่เป็น $O(|E|\ log\ |V|)$ อย่างไรก็ตาม เราจำเป็นต้องใช้เนื้อที่มากขึ้นและนี่อาจเป็นสิ่งที่มีความสำคัญในบางการประยุกต์ใช้งาน นอกจากนั้น เนื่องจากวิธีนี้ต้องใช้การทำงาน deleteMin เป็นจำนวน $|E|$ ครั้ง (แทนที่จะเป็น $|V|$) จึงทำให้ในทางปฏิบัติมันจะทำงานช้ากว่า

เราจะเห็นได้ว่าสำหรับปัญหาทั่ว ๆ ไปที่สามารถจำลองได้ด้วยกราฟ เช่น ปัญหาการสื่อสารคอมพิวเตอร์หรือปัญหาเกี่ยวกับการขนส่งมวลชนนั้น กราฟที่ใช้มักจะเป็นกราฟแบบ sparse graph คือ vertex เกือบทั้งหมดมี edge อยู่ 2 ถึง 3 edges เท่านั้น ดังนั้น จึงมีความสำคัญที่จะเลือกใช้โครงสร้าง priority queue เพื่อแก้ปัญหา

ถ้ากราฟมี negative edge costs แล้วก็ไม่สามารถใช้ Dijkstra's algorithm ได้ ปัญหาคือ เมื่อมี vertex u ตัวหนึ่งเป็น known แล้ว ก็เป็นไปได้ที่จะมี vertex v ที่เป็น unknown ตัวหนึ่งมีเส้นทางกลับมายัง u ที่มีค่า cost เป็นลบมาก ๆ ได้อีก ในกรณีเช่นนี้การเลือกใช้เส้นทางเดินจาก s ไปยัง v กลับไป u จะดีกว่าการเลือกเส้นทางจาก s ไป u โดยไม่ใช้ v

วิธีที่ดูเหมือนจะแก้ปัญหาดังกล่าวนี้ได้คือการบวกค่าคงที่ค่าหนึ่งเข้าไปในทุก ๆ edge เพื่อขจัดค่า cost ที่เป็นลบออกไป แล้วคำนวณค่า shortest path จากกราฟใหม่ที่ได้นั้น วิธีการนี้ไม่สามารถแก้ปัญหาได้ทั้งนี้เนื่องจากเส้นทางที่ประกอบด้วย edge ที่มีจำนวนมากกว่าก็จะมี cost มากกว่าเส้นทางที่มีจำนวน edge น้อยกว่า

เพื่อแก้ปัญหาเราจะใช้อัลกอริทึมที่ใช้สำหรับกราฟแบบ weighted และสำหรับกราฟแบบ unweighted ร่วมกันแต่จะมี running time เพิ่มขึ้นสูงมาก อัลกอริทึมของเราจะไม่ใช้ตัวแปร known อีกต่อไป ทั้งนี้เนื่องจากระหว่างการทำงานของอัลกอริทึมอาจจะมีการเปลี่ยนใจที่จะใช้เส้นทางที่ได้เลือกไว้แล้ว เราเริ่มต้นด้วยการบรรจุ s ลงใน queue จากนั้นในแต่ละ stage ของการทำงานจะให้ทำการ dequeue vertex v ตัวหนึ่งและค้นหา vertices w ทั้งหมดที่เป็น adjacent กับ v โดย vertex นี้ต้องมี dw > dv + cv,w และให้ update ค่า dw และ pw, แล้วบรรจุ w ลงใน queue ถ้ามันยังไม่ได้อยู่ใน queue โดยเราอาจใช้การตั้งค่า bit หนึ่ง ให้กับ vertex เพื่อเป็นตัวบ่งชี้ว่ามันอยู่ใน queue แล้วหรือไม่ ให้ทำซ้ำกระบวนการดังกล่าวนี้จนกว่า queue จะว่าง รูปที่ 9.33 แสดงการใช้อัลกอริทึมนี้ (เกือบสมบูรณ์)

ถึงแม้ว่าอัลกอริทึมที่กล่าวนี้จะสามารถใช้งานได้กับกราฟที่ไม่มี negative-cost cycles แต่การทำงานของโปรแกรมจากบรรทัดที่ 6 ถึงบรรทัดที่ 10 จะไม่ใช่เป็นการทำงาน 1 ครั้งต่อ 1 edge อีกต่อไป เพราะว่าแต่ละ vertex สามารถ dequeue ได้สูงสุคเป็นจำนวน |V| ครั้งด้วยกัน ดังนั้น running time ก็จะเป็น $O(|E|*|V|)$ โดยต้องมีการใช้ adjacency list จะเห็นว่า running time นี้สูงขึ้นมากแต่โชคดีที่ปัญหาในทางปฏิบัติจะไม่มี cost ที่เป็นค่าติดลบ ในกรณีที่กราฟมี negative-cost cycles ก็จะทำให้มีการทำงานวนรอบในลูปไม่รู้จบ เราสามารถเพิ่มเติมการบันทึกการนับจำนวนครั้งของการ dequeue ของแต่ละ vertex ลงระหว่างบรรทัดที่ 4 และ 5 และให้โปรแกรมหยุดทำงานเมื่อ vertex ใด ๆ มีจำนวนครั้งของ dequeue เท่ากับ |V| + 1

void	weighted_negative( Vertex s )
{
	    Queue q;
	    Vertex v, w;
/*1*/   q = new Queue( );
/*2*/   q.enqueue( s ); 		// enqueue the start vertex s 
/*3*/   while( !q.isEmpty )
	   {
/*4*/      v = q.dequeue( );
/*5*/      for each w adjacent to v
/*6*/          if  ( v.dist + cvw < w.dist )
		       {  /*update w */
/*7*/             w.dist = v.dist + cvw ;
/*8*/             w.path = v;
/*9*/             if ( w is not already in q )
/*10*/                q.enqueue( w );
		       }
	    }
}

รูปที่ 9.33 Pseudocode ของ weighted shortest-path algorithm ที่มี negative edge costs

ถ้าเรารู้ว่ากราฟเป็นแบบ acyclic เราสามารถปรับปรุง Dijkstra's algorithm ให้ดีขึ้นได้โดยการเปลี่ยนลำดับของการปรับเปลี่ยน vertices ให้เป็น known เรียกว่า vertex selection rule กฎใหม่คือการเลือก vertices ตามลำดับใน topological order การทำงานของอัลกอริทึมทำได้ในหนึ่งรอบการทำงาน (pass) เนื่องจากการเลือกและการปรับเปลี่ยนเกิดขึ้นในขณะเวลาเดียวกับในตอนที่กำลังทำงาน topological sort

กฎการเลือกนี้ทำงานได้ถูกต้องเนื่องจากเมื่อ vertex v ถูกเลือกนั้นระยะ dv ไม่สามารถลดน้อยลงได้อีกต่อไปแล้วเนื่องจากด้วยลำดับตาม topological ordering rule จะไม่มี incoming edges เกิดขึ้นจากโนดที่ยังเป็น unknown ได้

กฎการเลือกที่กล่าวนี้ไม่จำเป็นต้องใช้ priority queue และมี running time เป็น $O(|E| + |V|)$ เนื่องจากการเลือกใช้เวลาคงที่

เราสามารถใช้กราฟแบบ acyclic เพื่อสร้างแบบจำลองของปัญหาแบบที่เรียกว่า downhill skiing problem (เช่นต้องการเดินทางจากจุด a ไปยังจุด b บนเนินเขาที่มีข้อจำกัดว่าเราสามารถเดินทางลงเนินได้เท่านั้นซึ่งก็หมายความว่าจะไม่มีการวนรอบนั่นเอง) ตัวอย่างของการประยุกต์ใช้ที่เป็นไปได้อย่างหนึ่งคือการจำลองแบบ (nonreversible) ปฏิกิริยาทางเคมี โดยเราอาจให้ vertex โดยกำหนดให้แต่ละ vertex แทนสถานะทางเคมีหนึ่งและใช้ edge ที่ประกอบด้วย weight แทนจำนวนพลังงานที่ถูกปลดปล่อยออกมาก่อนมีการเปลี่ยนจากสถานะหนึ่งไปเป็นอีกสถานะหนึ่ง และถ้าการเปลี่ยนสถานะเกิดขึ้นได้เฉพาะจากสถานะที่มีพลังงานมากไปสู่สถานะที่มีพลังงานน้อยกว่าได้เท่านั้นก็หมายความว่าเราจะได้กราฟแบบ acyclic graphs

การใช้งาน acyclic graphs ที่สำคัญอย่างหนึ่งคือการทำการวิเคราะห์ที่เรียกว่า critical path analysis เราจะใช้กราฟในรูปที่ 9.34 เป็นตัวอย่าง แต่ละโนดในกราฟใช้แทนกิจกรรมที่ต้องทำและเวลาที่ต้องใช้ในการทำงานนั้นให้แล้วเสร็จ กราฟในรูปที่ 9.34 เรียกว่า activity-node graph ในกราฟนี้จะมี edges เป็นตัวแทนลำดับของความสัมพันธ์ดังนี้: edge (v, w) หมายความว่ากิจกรรม v ต้องแล้วเสร็จก่อนที่กิจกรรม w จะเริ่มต้นได้ ซึ่งหมายความว่ากราฟต้องไม่มีการวนรอบ (acyclic) และกิจกรรมใด ๆ ก็ตามที่ไม่ขึ้นต่อกันทั้งทางตรงและทางอ้อมก็สามารถดำเนินการไปได้อย่างคู่ขนานกัน

กราฟชนิดดังกล่าวนี้มักใช้สำหรับการจำลองโครงการก่อสร้าง ซึ่งจะใช้ช่วยตอบปัญหาสำคัญ ๆ หลายอย่างด้วยกัน เช่น หาเวลาที่เร็วที่สุดที่ใช้ในการทำโครงงานให้แล้วเสร็จ (earliest completion time) จากกราฟจะเห็นว่าคำตอบคือ 10 หน่วยเวลาตามเส้นทาง A, C, F, H ปัญหาที่สำคัญอีกอย่างคือ หาว่ามีกิจกรรมใดบ้างที่สามารถทำเสร็จช้าลงได้และช้าลงได้เป็นเวลาเท่าไรโดยไม่มีผลกระทบต่อเวลาที่น้อยที่สุดที่ใช้เพื่อให้โครงการแล้วเสร็จ เช่นความล่าช้าของกิจกรรมใดกิจกรรมหนึ่งของ A, C, F, หรือ H จะทำให้เวลาแล้วเสร็จของโครงการมากกว่า 10 หน่วยเวลา ในทางตรงข้ามกิจกรรม B สามารถเสร็จช้าลงได้สองหน่วยเวลาโดยที่ไม่ทำให้เวลาแล้วเสร็จของโครงการช้าลงไป

เพื่อจะสามารถคำนวณสิ่งที่กล่าวมาข้างบนนั้นได้เราจะต้องเปลี่ยน activity-node graph ให้ไปเป็น event-node graph โดยให้แต่ละ event สอดคล้องกับ (ใช้เป็นตัวแทนของ) กิจกรรมที่แล้วเสร็จกิจกรรมหนึ่งและกิจกรรมทั้งหมดที่ขึ้นต่อมัน การเข้าถึง Events จากโนด v ใน event-node graph ไม่อาจทำได้จนกว่า event v จะแล้วเสร็จสมบูรณ์แล้ว ใช้ dummy edges และ dummy nodes ในกรณีที่กิจกรรมนั้น ๆ ขึ้นต่อกิจกรรมอื่น ๆ หลายกิจกรรม เหตุที่ต้องทำเช่นนี้ก็เพื่อหลีกเลี่ยงความผิดพลาดของการขึ้นต่อกัน รูปที่ 9.35 เป็น event node graph ของกราฟของ activity-node graph ในรูปที่ 9.34

ในการคำนวณหาค่า earliest completion time ของโครงการเป็นเพียงการหาเส้นทางที่ยาวที่สุดจาก event แรกไปยัง event สุดท้าย เนื่องจาก event-node graph เป็นกราฟแบบ acyclic ดังนั้นจึงไม่ต้องกังวลกับการวนรอบ ในกรณีนี้เราสามารถปรับปรุงอัลกอริทึมของการหา shortest-path มาใช้เพื่อหา earliest completion time ของโนดทั้งหมดในกราฟได้ ถ้าให้ $EC_i$ เป็น earliest completion time สำหรับโนด i แล้ว เราจะใช้กฎดังนี้

\begin{align*} {EC}_1 & = 0\\ {EC}_w & =\max_{(v,w)\in E}{({EC}_v+c_{v,w})} \end{align*}

เราสามารถคำนวณค่าเวลาที่ช้าที่สุด (latest time), $LC_i$, ที่แต่ละ event ได้โดยไม่มีผลกระทบต่อเวลาที่แล้วเสร็จของโครงการ โดยใช้สูตร:

\begin{align*} {LC}_n & = EC_n\\ {LC}_v & = \min_{(v,w)\in E}{({LC}_w-c_{v,w})} \end{align*}

ค่าดังกล่าวเหล่านี้คำนวณได้ในเวลาที่เป็น linear time โดยต้องมีรายการ adjacent ทั้งหมดของแต่ละ vertex และรายการของ vertices ก่อนหน้าด้วย การคำนวณหา earliest completion times ของ vertices ทำได้โดยใช้ topological order และการคำนวณหา latest completion times หาได้โดย reverse topological order

slack time ของแต่ละ edge ใน event-node graph ก็คือเวลาที่สามารถล่าช้าลงได้ในการทำกิจกรรมนั้น ๆ ให้แล้วเสร็จโดยไม่ทำให้เวลาที่ใช้ทำงานทั้งโครงการให้แล้วเสร็จต้องล่าช้าออกไป ซึ่งก็คือ

$$Slack_{(v,w)} = LC_w – EC_v – c_{v,w}$$

รูปที่ 9.38 ตัวเลขที่ปรากฏอยู่ด้านบนของโนดคือค่าของ earliest completion times / latest completion times แสดง slack (ค่าตัวที่สามที่ปรากฏบน edge) ของแต่ละกิจกรรมใน event-node graph มีบางกิจกรรมที่มีค่า slack เป็นศูนย์ นั่นคือกิจกรรมนี้เป็น critical activities ที่จะต้องทำให้แล้วเสร็จตามเวลาที่กำหนดอยู่นั้น และในกราฟต้องมีอย่างน้อยหนึ่งเส้นทางที่กิจกรรมทั้งหมดมี slack เป็นศูนย์ และเส้นทางนี้ คือ critical path นั่นเอง

บางครั้งจำเป็นต้องหาเส้นทางที่สั้นที่สุดระหว่างคู่ของ vertices ทั้งหมดทุกคู่ vertices ในกราฟ ถึงแม้ว่าเราสามารถใช้อัลกอริทึมของ single-source shortest path แต่ก็ทำงานอัลกอริทึมนี้เป็นจำนวนถึง |V| ครั้ง แต่การใช้อัลกอริทึมของ dynamic programming algorithm จะสามารถแก้ปัญหานี้ได้ในเวลา $O(|V|^3)$ ในบทเรียนนี้จะไม่กล่าวถึงเรื่องนี้ ผู้สนใจสามารถศึกษาเองได้