single-source shortest paths

)مسألة اقصر المسارات (Single-source shortest paths)

بافتراض لدينا مخططا موجها G=(V,E)، كل حافة فيه لديها طولا موجبا وعقدة مميزة تدعى عقدة المصدر(source vertex)، فالمطلوب في هذه المسألة تحديد اقصر المسارات من s الى عقد المخطط الاخرى.
لان هذه المسألة تستدعي الترتيب مابين مجموعة جزئية من الحواف بين العقدة s والعقد الباقية لايجاد المسار الاقصر لذلك فهي تطابق نموذج الترتيب.
طريقة الطماع : يمكن حل هذه المسالة باستعمال تقنية طماع تدعى Dijkstra algorithm. تقوم هذه الخوارزمية بايجاد اقصر المسارات من العقدة s الى العقد الباقية من خلال توليد المسارات بترتيب تصاعدي نسبة الى أطوال مساراتهم.
للبساطة سوف نفترض ان V={1,2,…,n} و s=1، حيث يتم في البداية تقسيم مجموعة العقد الى مجموعتين X={1} و Y={2,3,…,n}. ان الهدف بعد ذلك هو جعل X تحتوي على العقد التي تم تحديد بعدها عن العقدة s مسبقا. وفي كل خطوة يتم انتقاء عقدة معينة وتحريكها الى المجموعة X حيث يرتبط بكل عقدة في المجموعة Y المقدار dist[y] والذي يمثل طول المسار الاقصرالذي يمر من خلال العقد في المجموعة X وحالما يتم تحريك عقدة معينة y من المجموعة Y الى المجموعة X يتم تحديث المقدار dist[y] لكل العقد والمجاورة للعقدة y .

الشكل التالي يوضح عمل الخوارزمية Dijkstra:



Algorithm Dijkstra( G, n):
Input:A weighted directed graph G=(V,E), where
V={1,2,…,n}.
Output:The distance from vertex 1 to every other vertex
in G.
1. X={1}; Y V-{1}; dist[1] 0
2. for y 2 to n
3. if y is adjacent to 1 then dist[y] c[1,y]
4. else dist[y]
5. end if
6. end for
7. for j 1 to n-1
8. Let y Y be such that dist[y] is minimum
9. X X {y}
10. Y Y-{y}
11. for each edge <y,w>
12. if w Y and dist[y]+c[y,w] < dist[w] then
13. dist[w] dist[y]+c[y,w]
14. end for
15.end for
16.return dist

تعقيدات الوقت:

الخطوة 1: تاخذ ?(n) .
الخطوة 2: تأخذ ?(n) .
الخطوتان 3و4: تأخذ O(n) .
الخطوة 7: تأخذ (n)?.
الخطوة 8: تأخذ ?(n2).
الخطوتان 9و10: تأخذ (n)?.
الخظوتان 11و12: تأخذ ) ?( .

الوقت الكلي للخوارزمية هو