การบ้าน : Dijkstra's Algorithm

ช่วยเขียน applet ที่ทำงานคล้าย ๆ applet ข้างล่างนี้หน่อย (ไม่จำเป็นต้องเหมือนเปี๊ยบ)
กดปุ่ม Random เพื่อสุ่มสร้างจุด 101 จุด (จะนำเมาส์ไปคลิกจุดเพิ่มก็ทำได้) เมื่อกดปุ่ม Play ก็จะเิริ่มหาวิถีสั้นสุดจากจุดแดงไปยังจุดอื่น ๆ ทั้งหมด

ข้างบนนี้เราถือว่ามี complete graph (เราไม่ได้แสดงเส้นเชื่อม เพราะจะแน่นไปหมด) โดยความยาวของเส้นเชื่อมมีค่าเป็นกำลังสองของระยะทางระหว่างจุด (หมายความว่าความยาวของเส้นเชื่อมระหว่างจุด i กับ j คือ (x_i-x_j)² + (y_i-y_j)²) ขอเน้นว่าความยาวเส้นเชื่อมไม่ได้เป็นระยะทางสั้นสุดแบบ euclid ระหว่างจุดสองจุดบนระนาบสองมิติ เพราะถ้าเป็นเช่นนั้น การหา single-source shortest paths ก็จะง่ายมาก ดังแสดงด้วย applet ข้างล่างนี้ (ลองคิดเล่น ๆ ก่อนดูนะว่าจะได้ผลอย่างไร ก่อนกดปุ่ม Random แล้ว Play ข้างล่างนี้

อ้อลืมบอกไปว่า การแสดงการทำงานทั้งสอง applets ข้างบนนี้ เราจงใจให้มีการหน่วงเวลาเล็กน้อย (ประมาณ 30ms) ทุกครั้งที่มีการลากเส้นเชื่อมที่เลือก เพราะต้องการให้เห็นการเติบโตของต้นไม้ที่หาได้ระหว่างการทำงาน

วิธีส่ง

เมื่อทำเสร็จ ให้นำ applet ที่พัฒนาขึ้นพร้อมเขียน web page เพื่อสาธิตการทำงาน แล้วไปวางไว้ที่ใคร ๆ ก็ชมได้ จากนั้น ส่ง source code พร้อม url ของ page ที่สาธิตการทำงานที่ว่านี้ มาให้ผมที่ somchaip@chula.ac.th โดยให้ mail มี subject ในรูปแบบดังนี้

HW327-01-xxxxxxxxxx ตามด้วยชื่อสกุล

โดยที่ xxxxxxxxxx คือรหัสนิสิต ให้เวลาสองอาทิตย์ หมดเขต 27 ส.ค. ศกนี้

ช้อแนะนำ

จะเลือกใช้โครงสร้างข้อมูลอะไรก็ไม่ว่ากัน แต่ต้องใช้อัลกอริทึมของ Dijkstra

ถ้ามีเวลาว่างสักอีก 10 นาที

ให้สังเกตว่าต้นไม้ที่ได้นั้นไม่ใช่ Minimum spanning tree (ลองคิดดู) ถ้าว่าง ๆ ก็ลองปรับ applet ที่ได้เขียนไปอีกนิดเดียวให้หา minimum spanning tree ด้วยอัลกอริทึมของ Prim นั้นง่ายนิดเดียว แก้เพียงสองสามบรรทัดเท่านั้นจากของ Dijkstra หรือถ้าจะปรับ applet ให้เป็นแบบข้างล่างนี้ให้ผู้ใช้เลือกเอา ก็น่าสนใจ

สมชาย ประสิทธิ์จูตระกูล (15/8/47)