stanford-oval/wikipedia huggingface dataset:
אלגוריתם דייקסטרה
סיבוכיות זמן ובחירת מבנה נתונים לתור הקדימויות > סיבוכיות זמן > ביצועים פרקטיים וניתוח מקרה ממוצע

ערימת פיבונאצי (רגילה או חזקה) ותור ברודאל אינם נפוצים בפרקטיקה, משום שהם מורכבים למימוש וברוב המקרים אינם מניבים ביצועים טובים יותר (על אף הסיבוכיות מקרה גרוע הטובה יותר). הסיבות לפער בין הביצועים האמפיריים לסיבוכיות מקרה גרוע ביותר נובעת מגורמים קבועים משמעותיים ש"מוחבאים" בסימון האסימפטוטי, ומפער בין המקרה הגרוע ביותר למקרים נפוצים יותר.
נבחן למשל את תור הקדימויות שנבחר בספריות קוד פופולריות: ערימה בינארית נבחרה בספריות בשפת פייתון (NetworkX), C#, ראסט, ו-Go; בעוד ש-Boost, ספריית C++ יעילה ופופולרית, משתמשת בערימה d-ארית (d=4). העדפה זו נתמכת גם על ידי מחקרים אקדמיים שביצעו מבחנים אמפיריים.
ניתוח מקרה ממוצע עוזר לתת הסבר תאורטי לפער בין הביצועים בפרקטיקה לסיבוכיות מקרה גרוע. במקרה הגרוע נעשה מספר יוצא דופן של קריאות ל-DECREASE_KEY, ביחס למקרה הממוצע. בממוצע, מספר הקריאות הנוספות ל-DECREASE_KEY (ביחס ל-EXTRACT_MIN) איננו מספיק כדי להצדיק את הגדלת הגורמים הקבועים שנדרשים עבור EXTRACT_MIN (כפי שקורה בערימת פיבונאצ'י).
גולדברג (אנ') וטרג'אן (1996) הראו שמספר הקריאות הצפוי ל-DECREASE_KEY חסום על ידי  O(V\ log(1+E/V)), במודל בו ההנחה היחידה היא שעבור כל קודקוד, משקלי הקשתות מוגרלות באופן בלתי תלוי מאותה התפלגות. זמן הריצה הצפוי של אלגוריתם דייקסטרה עם ערימה בינארית הוא  O(E+V\ logV\ log(1+E/V)) לעומת  O(E+V\ logV) עם ערימת פיבונאצי. לערימת פיבונאצ'י יש יתרון (אסימפטוטי) רק כאשר E=o(V\ logV\ loglogV), ואפילו אז היחס בין זמני הריצה הוא רק  o(loglogV), שבפרקטיקה זניח לעומת הגורמים הקבועים בערימת פיבונאצ'י.
יש וריאציה של אלגוריתם דייקסטרה בעלת זמן ריצה ממוצע ליניארי (כאשר ידוע חסם למשקל המקסימלי, והמשקלים מתפלגים אחיד).
סיבוכיות זמן ובחירת מבנה נתונים לתור הקדימויות > סיבוכיות זמן > משקלים שלמים

אם המשקלים הם מספרים שלמים, יש תורי קדימויות מיוחדים שיכולים לשפר את הסיבוכיות.
תור דלי (אנ') מאפשר לדייקסטרה לרוץ בזמן O(E+V*C), שכן הוא מאפשר לבצע DECREASE_KEY ב-O(1) ו-EXTRACT_MIN ב- O({\sqrt {C}}). תור דלי מנצל את כך שניתן לחלק את המפתחות בתור הקדימויות בין C+1 דליים (כאשר C הוא המשקל המקסימלי בגרף), שכל אחד מכיל רשימה מקושרת של קודקודים בעלי מפתח זהה. ייתכן שהמפתח המזוהה עם דלי ישתנה, אך תמיד יהיה צורך רק ב-C+1 דליים.
המפתחות בתור תמיד יהיו בטווח בין המינימום הנוכחי  min ל- min+C, או שהמפתח אינסופי (האלגוריתם טרם סרק את הקודקוד). נוכיח טענה זו כשמורת לולאה (אנ'): באתחול טענה זו נכונה באופן טריויאלי. בכל איטרציה, בתחילתה מבוצע EXTRACT_MIN שאיננו מקטין את המינימום, ולכן לא מפר את השמורה; ו-DECREASE_KEY גם איננו מפר את השמורה, שכן המפתח החדש הוא:  DistEst[u]+weight(u,v)=min+weight(u,v)\leq min+C.
תור דלי הוא דוגמה בסיסית לתורי קדימויות מונוטוניים (אנ'), שהם תורי קדימויות המותאמים למקרים בהם ערך המינימום לא קוטן. הנחה זו מתאימה לדייקסטרה, שסורק קודקודים בסדר עולה של מרחקם מהמקור.
תור קדימויות מונוטוני נוסף הוא ערימת בסיס (אנ'), שמשפר את תור דלי בכך שדליים מכילים מספר מפתחות, אך דליים של מפתחות שקרובים יותר למינימום יהיו "צרים" יותר (יכילו פחות מפתחות). זמן הריצה של דייקסטרה עם ערימת בסיס הוא  O(E+VlogC), ואם משתמשים בערימת בסיס עם שתי רמות מתקבל זמן ריצה של  O(E+VlogC/loglogC).
עבור גרפים מכוונים, סיבוכיות המקרה הגרוע הטובה ביותר הושגה על ידי Thorup (אנ') ב-2004: (O(E+Vloglog(min{V,C}). יש וריאציה של דייקסטרה בעלת זמן ריצה ממוצע ליניארי O(E). עבור גרפים לא מכוונים, ישנה אפילו וריאציה שרצה ב-O(E) במקרה הגרוע.
| מבנה נתונים | EXTRACT_MIN | DECREASE_KEY | אלגוריתם דייקסטרה |
| --- | --- | --- | --- |
| תור דלי (שכבה אחת) | O(C) | O(1) | O(E+VC) |
| תור דלי (2 שכבות) | O(sqrt(C)) | O(1) |  O(E+V{\sqrt {C}}) |
| תור דלי עם k שכבות |  O(k+C^{1/k}) | O(k) |  O(kE+V(k+C^{1/k})) |
| ערימת בסיס (שכבה אחת) | O(logC) | O(1) |  O(E+V\ logC) |
| ערימת בסיס (2 שכבות) |  O(logC/\ loglogC) | O(1) |  O(E+V\ logC/\ loglogC) |
| הערימה של Thorup ‏(2004) | O(1) | O(loglogV) | O(EloglogV) |
יישומים

פרק זה לוקה בחסר. אנא תרמו לוויקיפדיה ו. ייתכן שתמצאו פירוט בדף השיחה.
השוואה לאלגוריתמים אחרים > דייקסטרה כהכללה של אלגוריתם חיפוש לרוחב עבור גרפים ממושקלים

| --- | --- |
 :  ראו גם – אלגוריתם חיפוש לרוחב
ניתן לראות את אלגוריתם דייקסטרה כהכללה של אלגוריתם חיפוש לרוחב עבור גרפים ממושקלים. בפרט, אלגוריתם דייקסטרה שקול לאלגוריתם חיפוש לרוחב בגרף שבו כל המשקלים שווים ל-1.
סיבוכיות אלגוריתם חיפוש לרוחב היא O(V+E), בהשוואה ל-O(VlogV+E) של דייקסטרה. כלומר, בעיית המסלול הקצר ביותר בגרף לא ממושקל היא קלה יותר מאשר בגרף ממושקל.
אלגוריתם חיפוש לרוחב יכול למצוא מסלול קצר ביותר בגרף ממושקל באופן הבא: ניצור גרף חדש, G', שבו עבור כל קשת e=uv ניצור w(e) קשתות חדשות בעלות משקל=1 המחברות את u ו-v דרך w(e)-1 "קודקודי דמה" חדשים. אך שיטה זו מגדילה משמעותית את גודל הגרף שעליו צריך לבצע חיפוש. ניתן לראות את דייקסטרה כאופטימיזציה של שיטה זו, אשר אינה דורשת הגדלה מלאכותית של הגרף.
השוואה לאלגוריתמים אחרים > גרפים בעלי משקלים שליליים

האלגוריתם הקלאסי לבעיה זו הוא אלגוריתם בלמן-פורד. נהוג ללמוד אלגוריתם זה לצד דייקסטרה בקורסי מבוא לאלגוריתמים רבים. בלמן-פורד דומה במובנים מסוימים לדייקסטרה: גם הוא מיישם את התבנית האלגוריתמית של פורד לאלגוריתמים למציאת המסלול הקצר ביותר (ראו בפרק ההיסטוריה), וגם הוא אלגוריתם חמדן המשתמש בתכנון דינמי.
סיבוכיות הזמן של אלגוריתם בלמן-פורד היא O(VE). זו הייתה הסיבוכיות מקרה גרוע הטובה ביותר שהייתה ידועה עד ל-2023, אז פורסם אלגוריתם אקראי בעל סיבוכיות זמן של Õ(EV^8/9) בסבירות גבוהה. כלומר, בעיית המסלול הקצר ביותר היא קשה יותר כאשר יש בגרף משקלים שליליים.
האלגוריתם של ג'ונסון מוצא מסלולים קצרים ביותר בין כל זוג קודקודים בגרף, באמצעות שילוב כוחות בין בלמן-פורד ודייקסטרה.
השוואה לאלגוריתמים אחרים > שימוש ביוריסטיקות - A*

ניתן לראות את אלגוריתם A* כוראיציה של דייקסטרה שמשתמשת בפונקציית יוריסטיקה כדי למצוא יותר מהר את המסלול הקצר ביותר. באלגוריתם A* נשלף הקודוקד v שממזער את DistEst[v]+h(v), כאשר h היא פונקציית יוריסטיקה האומדת את המרחק מ-v לקודקוד היעד. השוו זאת לדייקסטרה, אשר שולף את הקודקוד שממזער את DistEst[v] בלבד. דייקסטרה שקול ל-A* אם בוחרים את פונקציית היוריסטיקה h(x)=0.
לעומת דייקסטרה, A* נועד למצוא את המסלול הקצר ביותר בין זוג קודקודים ספציפי, בעוד שדייקסטרה מסוגל לפתור גם את בעיית כל המסלולים הקצרים ממקור יחיד.
במקרים רבים היוריסטיקה מאפשרת לאלגוריתם לנצל ידע חיצוני על הקודקודים. למשל, אם הגרף מייצג מיקומים, ניתן להשתמש במרחק האוקלידי בין v ליעד בתור פונקציית היוריסטיקה. כך אלגוריתם החיפוש יודע לוותר מראש על כיווני חיפוש מיותרים, ו"לכוון" ליעד. עם זאת, כדי להבטיח פלט נכון, ישנם הגבלות מסוימות על פונקציית היוריסטיקה (ראו בערך על האלגוריתם), ועבור קלטים מסוימים פונקציית המרחק האוקלידי לא מקיימת תנאים אלו.
השוואה לאלגוריתמים אחרים > מקרים פרטיים

עבור גרף לא מכוון, יש אלגוריתם אקראי שרץ ב- O(E{\sqrt {logV\cdot loglogV}}) בהסתברות גבוהה (אנ') (כלומר, כשהקלט שואף לאינסוף, ההסתברות שואפת ל-1). האלגוריתם הוא וריאציה על אלגוריתם דייקסטרה, שבה רק תת-קבוצה מצומצמת של הקודקודים נמצאת בתור הקדימויות.
בנוסף, ישנם מקרים פרטיים של גרפים מכוונים בהם ניתן למצוא אלגוריתם בעל סיבוכיות עדיפה מדייקסטרה. ישנם גם שיפורים עבור גרפים מישוריים, גרפים חסרי מעגלים, וקלט גאומטרי.
המצאת האלגוריתם

המחקר המתמטי המודרני על מציאת המסלול הקל ביותר בגרף בעל משקלים חיוביים החל בשנות החמישים של המאה ה-20. ב-1956 חוקר ממכון ראנד פרסם תבנית לאלגוריתמים למציאת המסלול הקל ביותר, שאלגוריתם דייקסטרה מיישם. אלגוריתם דייקסטרה פורסם באופן בלתי תלוי ב-1957 על ידי חוקרים ממכון CASE, ב-1959 בידי אדסחר דייקסטרה (שהגה את האלגוריתם כבר ב-1956) וב-1960 על ידי אנשי חקר ביצועים. בנוסף, בתעשייה נעשה שימוש באלגוריתם זהה או דומה, לפחות בפרויקט אחד.
המצאת האלגוריתם > פורד (1956): תבנית לאלגוריתמים למציאת המסלול הקל ביותר

| --- | --- |
 :  ראו גם – אלגוריתם בלמן-פורד (על שמו של פורד)
ב-1956 ל"ר פורד ג'וניור (אנ') ממכון ראנד תיאר תבנית לאלגוריתמים למציאת המסלול הקל ביותר. לתבנית זו תואמים אלגוריתם דייקסטרה, כמו גם אלגוריתם בלמן-פורד המסוגל לעבוד עם משקלים שליליים (וקרוי על שם פורד בזכות תבנית זו). אך התבנית היא כללית, ויכולה להתאים באותה מידה גם לאלגוריתמים בעלי סיבוכיות אקספוננציאלית.

התבנית של פורד:
נסמן ב- d(v) פונקציה המחזירה את הערכת המרחק מצומת המקור  s לכל צומת אחרת  v (בדומה ל-DistEst בפסודו-קוד בתחילת הערך).
אתחול: קבע  d(s)=0 ו- d(v)=\infty  לכל  v\neq s.
לולאה: באופן איטרטיבי, בחר קשת  uv המקיימת  d(v)>d(u)+w(uv), וקבע  d(v):=d(u)+w(u,v).
פורד לא ציין אף כלל לבחירת הקשת  uv. אלגוריתם דייקסטרה בוחר את הקשת  uv שממזערת את  d(u).
המצאת האלגוריתם > אדסחר דייסקטרה (1956\1959)

| --- | --- |
 :  ראו גם – אדסחר דייקסטרה
דייסקטרה תכנן את האלגוריתם ב-1956, במטרה להציג את יכולות המחשב ARMAC (הו') בטקס החניכה החגיגי שלו. דייסקטרה רצה לבחור בעיה אלגוריתמית שגם קהל לא מתמטי יוכל להבין. הבעיה שבחר בה הייתה מציאת המסלול הקצר ביותר בין ערים הולנדיות. דייסקטרה מספר שהוא תכנן את האלגוריתם בכ-20 דקות, בזמן הפסקת קפה שלקח כשעשה קניות עם ארוסתו. דייסקטרה האמין שדווקא משום שלא היה יכול להשתמש בעפרון ונייר, הוא אולץ לחשוב על אלגוריתם פשוט ואלגנטי.
דייסקטרה פרסם את האלגוריתם רק כ-3 שנים לאחר המצאתו, ב-1959. תיאור האלגוריתם התפרס על פני עמוד אחד בלבד, מתוך מאמר בן 2.5 עמודים שכלל גם תיאור של אלגוריתם גרפי נוסף. המאמר לא עסק בבחירת מימוש לתור הקדימויות (למעשה דייקסטרא כלל לא השתמש במונח זה), ולכן בטקסטים מודרניים לעיתים מתייחסים לסיבוכיות הזמן של האלגוריתם המקורי כ- O(|V|^{2}).
דייסקטרה אמר שב-1956 "אלגוריתם למציאת המסלול הקל ביותר בקושי נחשב למתמטיקה: יש מספר סופי של מסלולים מ-A ל-B וברור שאחד מהם הוא הקצר ביותר, אז על מה כל המהומה?". דייקסטרא החליט לפרסם מאמר על האלגוריתם 3 שנים לאחר המצאתו, כאשר עורך של כתב עת חדש, שעסק גם בנושאים שכיום ייחשבו כחלק ממדעי המחשב, פנה לדייסקטרה ושאל אם יש לו מה לתרום לכתב העת.
בתחילת שנות השישים דייסקטרה נתקל לראשונה בטקסט שקורא לאלגוריתם על שמו, בספר לימוד גרמני.
המצאת האלגוריתם > מאמרים שפורסמו במקביל

במקביל לדייקסטרה, חוקרים אחרים פיתחו את האלגוריתם ופרסמו אותו.
ב-1957 התפרסם תיאור של האלגוריתם במאמר של חוקרים ממכון CASE (אנ') באוהיו. התיאור פורסם בדו"ח שנתי של פרויקט מחקר שבוצע עבור ה-Combat Development Department ב-Electronic Proving Ground של צבא ארצות הברית. המאמר לא התבלט בזמן פרסומו, אך בהסתכלות היסטורית הוא זכור כתגלית עצמאית של אלגוריתם דייקסטרה.
ב-1960 Whiting & Hillier פרסמו מאמר נוסף שתיאר את האלגוריתם. המאמר פורסם בכתב עת העוסק בחקר ביצועים, והמוטיבציה נבעה מבעיות תחבורה ותקשורת.
Dantzig פרסם אלגוריתם דומה ב-1960, אך הוא היה פחות יעיל.
המצאת האלגוריתם > LEO 1 ו-British Railways ‏(1955-1956)

LEO 1 היה מחשב בריטי שהחל לפעול ב-1951. המחשב היה שייך לתאגיד המזון J. Lyons and Co., שגם השכיר את שירותי המחשוב לגורמים אחרים. ב-1955 British Railways (אנ') שכרו את שירותי המחשוב לטובת חישוב המרחק בין תחנות הרכבת שלהם. בניסוח גרפי, זוהי הבעיה של מציאת המסלול הקצר ביותר בין כל זוג קודקודים. על הבעיה עבד רוג'ר קולמן, תחת ניהולו של דייוויד קמינר.
כחלק מפתרון הבעיה, פותח אלגוריתם שאפשר להחשיב כגרסה מוקדמת של אלגוריתם דייסקטרה. עם זאת, האלגוריתם של קולמן כלל הרבה התאמות לבעיה הספציפית של British Railways. בנוסף, האלגוריתם מעולם לא פורסם, והידע שלנו עליו מתבסס על ראיונות שחובבי היסטוריית מחשוב ערכו עם קולמן בשנות האלפיים. קולמן לא המשיך לעסוק במדעי המחשב, ועד לאותם ראיונות הוא לא ידע על קיומו של האלגוריתם של דייסקטרה ועל החשיבות ההיסטורית של המצאתו שלו.
ראו גם

בעיית המסלול הארוך ביותר
ביאורים

↑  בהקשר הנכוחי, בגרף מכוון "שכן" משמעותו שיש קשת שיוצאת מהקודקוד הראשון ונכנסת לקודקוד השכן.
↑  ההוכחה היא עבור בעיית המסלולים הקלים ממקור יחיד לכל הקודקודים בגרף. ההוכחה דומה עבור הגרסה שבה האלגוריתם מסתיים לאחר שליפת קודקוד יעד מסוים (בעיית המסלול הקל ממקור יחיד ליעד יחיד).
↑  האיור מספק אינטואיציה, אך ישנם מקרים שבהם הוא איננו מדויק: ייתכן ש-x=u, y=v או שיש חפיפה בין הקודקודים s,u,x. בנוסף ייתכן שבמסלול מ-y ל-v יש קודקודים נוספים מבין הקודקודים שבוקרו.
↑  רוב הספרות מתמקדת בהרצה של דייקסטרה על גרף מכוון. אם הגרף לא מכוון, ניתן ליצור גרף חדש שבו כל קשת u-v משוכפלת פעמיים, עבור שני הכיוונים (u->v, v->u). זהו הבדל של קבוע בגודל הקלט, ולכן רוב תוצאות הסיבוכיות עבור גרפים מכוונים תקפים גם לגרפים לא מכוונים. אך תוצאות לגבי אופטימליות, ביצועים פרקטיים וזמן ממוצע לא בהכרח מדויקות.
1 2  אם הגרף לא קשיר, אז הסיבוכיות היא O((V+E)logV). אם הגרף קשיר (כפי שנהוג להניח בטקסטים רבים), אז E=\Omega(V) ולכן ניתן להתייחס לסיבוכיות כ-O(ElogV).
↑  ה-Comparison-addition model, שבו מותר לבצע השוואות וסכימות של המשקלים. ראה התייחסות ל-RAM model בתת-הפרק על משקלים שלמים.
↑  לא ניתן להתחמק מהופעת E בסיבוכיות משום שהאלגוריתם חייב לסרוק את כל הקשתות בגרף (במקרה הגרוע).
↑  ניתן להניח שבקלט יש רשימת קודקודים.
↑  ציינתי ספריות רלוונטיות מתוך רשימה של github repository בעלות מעל ל-2,500 כוכבים, ושמתויגות ב-graph-algorithms (ראה רשימה כאן).
↑  האנומליה היא ספריית הג'אווה JGraphT, שמתממשת ב-Pairing heap (אנ') (ראה קוד מקור). ספריית ג'אווה פופולרית נוספת, AlgoDS, מאפשרת לבחור בין מימוש מבוסס רשימה, ערימה בינארית או ערימת פיבונאצי (ראה קוד מקור).
↑  אם אין תלות בין המשקלים, זמן הריצה מתקיים בסבירות גבוהה.
↑  אלא אם מצוין אחרת, האלגוריתמים בפרק זה מניחים מודל חישובי שנקרא מכונת RAM (אנ'). בניסוח לא פורמלי, במודל זה הקלט "נכנס" במילים בזיכרון RAM (בניגוד למספרים ממשיים, שבהם עסקנו עד כה). בנוסף ניתן לבצע על המשקלים פעולות אריתמטיות ופעולות בסיסיות על סיביות, בדומה למעבד סטנדרטי. ראו למשל כאן.
↑  מימוש של דייקסטרה באמצעות תור דלי נקרא גם אלגוריתם דייאל (Dial's algorithm), כהוקרה למאמר של רוברט ב. דייאל מ-1969. מבנה הנתונים הוצע באופן בלתי תלוי גם על ידי רוברט ואגנר ב-1976 ויפים דיניץ (אנ') ב-1978.
↑  ערימות בסיס הוצעו ב-1990 על ידי Ahuja, Mehlhorn, Orlin & Tarjan, על בסיס מחקר של דונלד ג'ונסון מ-1977.
↑  האלגוריתם מניח שניתן לבצע כפל מספרים בזמן קבוע. אחרת, הסיבוכיות מתדרדת ל-O(E+V(loglogmin{V,C})^(1+epsilon)).
↑  ישנו גם אלגוריתם בזמן ליניארי O(E), אך הוא מניח מודל חישובי ייחודי שלא רלוונטי לאף ארכיטקטורת מחשבים מוכרת. ראה כאן בעמוד 1 ו-כאן.
↑  משמעות הסימון Õ (אנ') היא O כאשר מתייחסים לגורמים לוגריתמיים כזניחים. כלומר  f(n)\in {\tilde {O}}(g(n)) הוא כתיב מקוצר של  \exists k:f(n)\in O(g(n)\log ^{k}n) (קורמן ושות', עמ' 73-74)
↑  הגרף הכיל 64 קודקודים, שכל אחד מהם מייצג עיר בהולנד.
מטרון (קומיקס)

| --- | --- |

מטרון, כפי שהופיע על עטיפה אלטרנטיבית לחוברת Justice League Vol.2 #40 מיוני 2015. אמנות מאת אלכס גארנר.
 סוג:  נבל-על
 הוצאה לאור:  DC קומיקס
 הופעה ראשונה:  תור הארד של הקומיקס: New Gods #1 (מרץ 1971) לאחר פלאשפוינט: New Gods: Godhead #1 (דצמבר 2014)
 הופעה אחרונה:  תור הארד של הקומיקס: Death of the New Gods #7 (מאי 2008)
 יוצרים:  ג'ק קירבי
 מידע
 סטטוס:  פעיל
 גזע:  האלים החדשים
 מקצוע:  חוקר ארצות, מחפש אחר ידע
 כוחות:  חיי נצח, תכונות פיזיות על-אנושיות, סופר אינטלקט, ידע אוניברסלי, יכולות אלוהיות לא מוגדרות, שימוש בכיסא מוביוס המאפשר לו לנסוע בזמן, בחלל החיצון ובממדים אחרים.
 חבר בקבוצה:  מועצת השמונה
מטרון (באנגלית: Metron) הוא דמות בדיונית של נבל-על המופיעה בחוברות הקומיקס האלים החדשים בהוצאת DC קומיקס. הדמות הופיעה לראשונה בחוברת New Gods #1 מפברואר-מרץ 1971, והיא נוצרה על ידי הכתב ג'ק קירבי עבור סדרת העולם הרביעי שלו ב-DC קומיקס. דמותו של מטרון התבססה על דמותו של ספוק ממסע בין כוכבים, אותו גילם השחקן לאונרד נימוי. הדמות עוצבה כמי שתחליף צד לעיתים קרובות בין ניו ג'נסיס לאפוקוליפס.
כוחות ויכולות

כמו רוב האלים החדשים, למטרון פיזיולוגיה מתקדמת המספקת לו כוח וסיבולת על אנושית והוא חסין בפני כל המחלות, בהיותו למעשה בן אלמוות. מטרון הוא סופר גאון שחקר את היקום וצבר כמות עצומה של ידע מה שאיפשר לו ליצור פלאים טכנולוגיים לדוגמת טכנולוגיית "צינור בום" (Boom Tube) ששימשה את האלים החדשים לטלפורטציה של מרחקים עצומים. מטרון נוסע בכיסא המוביוס המעופף שלו, המאפשר לו לנסוע בזמן, בחלל החיצון ובממדים אחרים. קרן הגרירה שלו חזקות מספיק כדי לשאת כוכב לכת מאחורי הכיסא ויכולות ליצור קיר אנרגיה בלתי חדיר.
גרסאות אחרות

בקו העלילה של JLA Rock of Ages, מופיע מטרון מטורף ומרושע מעתיד חלופי, משתלט על כדור הארץ ואולי על היקום כולו. הוא מובס כאשר באטמן טוען שהפער היחיד בידע שלו הוא הבורות שלו לגבי מה זה אומר להיות אנושי, מה שמניע אותו להשתמש בכוחותיו כדי לוותר על הכוחות כמו אל שלו, מה שמאפשר לבאטמן להביס אותו באגרוף בודד.
במיני סדרה Seven Soldiers של גרנט מוריסון, מטרון מופיע כמשותק וחסר בית בכיסא גלגלים, לאחר שהודח מ"העולם הרביעי" כתוצאה מניצחון דארקסייד במלחמה בין אפוקוליפס לניו ג'נסיס. הוא נראה משחק שחמט עם הרוכב השחור, ולפעמים את כיסא הגלגלים שלו דוחף אוריון. בעוד שהסיפור הזה מתרחש בהמשכיות קבועה, הקטע שבו מטרון והאלים החדשים האחרים מופיעים במצב זה מתגלה כאחד מסדרה של עולמות אפשריים שחווה שילה נורמן, ולא ההווה האמיתי.
מטרון גורם להסטת החללית של סופרמן מכדור הארץ לאפוקוליפס בקומיקס Elseworld Superman: The Dark Side .
אזכורים במדיות אחרות > טלוויזיה

מטרון הופיע בסופרמן: סדרת האנימציה ללא דיבור. בפרק "אפוקוליפס. . . עכשיו!", הוא מוצג ברקע כאשר אוריון מביא את כל החיילים של ניו ג'נסיס כדי להדוף את דארקסייד מכדור הארץ.
מטרון מופיע בליגת הצדק: ללא גבלות, בדיבובו של דניאל דיי קים . בשני הפרקים האחרונים "חי!" ו"המשחית", הוא מנסה להזהיר את לקס לות'ר לא להחיות את ברייניאק, בטענה שמה שלקס יעשה ישפיע על היקום. כאשר לות'ור מתעלם ממטרון ומתקדם, דארקסייד בסופו של דבר קם לתחייה עם טכנולוגיה משופרת של ברייניאק. מטרון מאוחר יותר מספק ללקס את האמצעים להביס את דארקסייד על ידי לקיחת לות'ור לחומת המקור כדי להשיג את משוואת האנטי-חיים.
מטרון מופיע בעונה השלישית של ליגת הצדק - הדור הבא בפרק "שיחות שקטות", בדיבובו של פיל למאר. ברק שחור, וסופרבוי מחפשים את מטרון בשביל להשתמש בכיסא המוביוס שלו כדי להציל את ויקטור סטון מפני קופסת אב. מטרון רק מלווה אותם רק כדי לראות את ויקטור מת, וכתוצאה מכך סופרבוי מסיר אותו בכוח מהכיסא וברק שחור מבטל את יכולתו כדי שוויקטור יוכל להיות מחובר לכיסא.
אזכורים במדיות אחרות > סרטים

בליגת הצדק: אלים ומפלצות, לקס לות'ר הנכה וככל הנראה המשותק (בדיבובו של ג'ייסון אייזק) הופך לגרסה של מטרון.
כיסא המוביוס של מטרון מופיע בליגת הצדק האפל: מלחמת אפוקליפס, שעליו באטמן יושב אחרי שדארקסייד השתלט על כדור הארץ.
הערות שוליים

↑  Cowsill, Alan; Irvine, Alex; Korte, Steve; Manning, Matt; Wiacek, Win; Wilson, Sven (2016). The DC Comics Encyclopedia: The Definitive Guide to the Characters of the DC Universe. DK Publishing. p. 201. ISBN 978-1-4654-5357-0.
↑  Sacks, Jason; Dallas, Keith (2014). American Comic Book Chronicles: The 1970s. TwoMorrows Publishing. p. 39. ISBN 978-1605490564.
↑  Final Crisis #1 (July 2008). DC Comics.
↑  Final Crisis #6. DC Comics.
↑  Final Crisis #7. DC Comics.
↑  Green Lantern #35 (October 2014). DC Comics.
↑  Justice League vol. 2 #40 (April 2015). DC Comics.
↑  Justice League vol. 2 #42 (July 2015). DC Comics.
↑  Justice League vol. 2 #50 (May 2016). DC Comics.
↑  Dark Nights: Death Metal: Rise of a New God #1 (2020). DC Comics.
↑  The DC Comics Encyclopedia. Dorling Kindersley Limited. 2004. p. 202. ISBN 0-7566-0592-X.
↑  Seven Soldiers: Mister Miracle #4. DC Comics.
↑  Rich Fogel & Bruce Timm (writers); Dan Riba (director) (1998-02-14). "Apokolips...Now! (Part 2)". Superman: The Animated Series. Season 2. Episode 26. The WB.
↑  Matt Wayne (writer); Dan Riba (director) (2006-05-06). "Alive!". Justice League Unlimited. Season 3. Episode 12. Cartoon Network.
↑  Dwayne McDuffie (writer); Joaquim Dos Santos (director) (2006-05-13). "Destroyer". Justice League Unlimited. Season 3. Episode 13. Cartoon Network.
מועצה אזורית ערבות הירדן

אנדרטת הבקעה בתכנונו של הפסל יגאל תומרקין, הממוקמת סמוך למושב פצאל
מועצה אזורית ערבות הירדן היא מועצה אזורית במחוז יהודה ושומרון, בבקעת הירדן. בעוד זהו שמה במסמכים רשמיים של הממשלה, היא נקראת "מועצה אזורית בקעת הירדן" במסמכיה של המועצה האזורית עצמה. בתחומי המועצה 21 יישובים, ממוצע המרחקים בין יישובי המועצה הוא 18.9 ק"מ.
כל יישוביה הם התנחלויות המצויות ממזרח לקו הירוק. בדומה לשאר המועצות האזוריות ביהודה ושומרון, שטח השיפוט של המועצה כולל רק את שטחי היישובים היהודיים, ללא רצף קרקעי ביניהם. ישובי המועצה נמצאים בשטח המשתרע על 860 אלף דונם, ממורדות הרי השומרון ועד לנהר הירדן.

לפי נתוני הלשכה המרכזית לסטטיסטיקה (הלמ"ס) נכון לסוף דצמבר 2024 (אומדן), מתגוררים במועצה אזורית ערבות הירדן 7,608 תושבים, מתוכם 7,264 תושבי ישראל (מקום 208 בדירוג רשויות מקומיות בישראל).   אחוז הזכאים לתעודת בגרות מבין תלמידי כיתות י"ב בשנת ה'תשפ"ב (2021-‏2022) היה 82.6%. השכר החודשי הממוצע של שכיר במשך שנת 2021 היה 10,069 ש"ח (ממוצע ארצי: 11,330 ש"ח).
בשטח המועצה האזורית ערבות הירדן אין עיר מחוז. היישוב הישראלי הגדול ביותר באזור הוא מעלה אפרים, שאינו חלק מהמועצה האזורית אלא מוגדר כמועצה מקומית עצמאית שהוקמה בצו של צה"ל. המועצה האזורית גובלת בשטח העיר הפלסטינית יריחו וסביבותיה.
באוגוסט 2023 הודיע שר הפנים משה ארבל על בחינת איחודן של רשויות מקומיות, כולל הצעה לאיחוד מועצה מקומית מעלה אפרים ומועצה אזורית מגילות ים המלח עם מועצה אזורית ערבות הירדן, והנחה כי תהליך הבחינה יחל לאחר הבחירות לרשויות המקומיות. ביולי 2024 חתם מנכ"ל משרד הפנים רונן פרץ על כתב מינוי ועדה גאוגרפית לבחינת מעמד מוניציפלי ואיחוד רשויות מקומיות אלה.
מרכז אזורי שלומציון

המועצה הוקמה ב-1980. משרדי המועצה ממוקמים במרכז אזורי "שלומציון", שצמוד לכביש 90, בין משואה ליפית. שם נמצאים גם שני בתי ספר יסודיים, מתנ"ס אזורי, יד לבנים וקריית ביטחון הכוללת מוקד ביטחון אזורי, תחנת כיבוי אש, תחנת מד"א ונקודת שיטור קהילתי.
ישנו מרכז אזורי נוסף מדרום למושב יפית, הידוע בכינוי "מפגש הבקעה" ומשמש כמרכז מסחרי אזורי, ובו: קופת חולים (כללית), בית קפה, סופרמרקט ועוד.
ראשי המועצה

ישראל נדיבי, תושב מחולה, כיהן שתי קדנציות (1979–1990)
דוד לוי, תושב ארגמן, כיהן שלוש קדנציות
דובי טל, תושב שדמות מחולה, כיהן קדנציה אחת
דוד אלחייני, תושב ארגמן – ראש המועצה הנוכחי
יישובי המועצה

| מספר | צורת היישוב | יישוב | שנת הקמה | מספר תושבים (2023) |
| --- | --- | --- | --- | --- |
| 1 | מושב | ארגמן | 1968 | 160 |
| 2 | מושב | בקעות | 1972 | 247 |
| 3 | מאחז | גבעת סלעית | 2001 | 20 משפחות |
| 4 | מושב | גיתית | 1972 | 567 |
| 5 | קיבוץ | גלגל | 1970 | 209 |
| 6 | יישוב קהילתי | חמדת | 1979 | 386 |
| 7 | מושב | חמרה | 1971 | 271 |
| 8 | מושב | ייט"ב | 1970 | 199 |
| 9 | מושב | יפית | 1980 | 279 |
| 10 | יישוב קהילתי | מבואות יריחו | 1999 | 538 |
| 11 | מושב | מחולה | 1967 | 760 |
| 12 | מושב | מכורה | 1973 | 250 |
| 13 | מושב | משואה | 1969 | 434 |
| 14 | יישוב קהילתי | משכיות | 2004 | 389 |
| 15 | מושב | נעמ"ה | 1982 | 311 |
| 16 | קיבוץ | נערן | 1971 | 146 |
| 17 | מושב | נתיב הגדוד | 1975 | 214 |
| 18 | מושב | פצאל | 1970 | 534 |
| 19 | מושב | רועי | 1976 | 154 |
| 20 | יישוב קהילתי | רותם | 2001 | 311 |
| 21 | מושב |  שדמות מחולה | 1984 | 731 |
| 22 | מושב | תומר | 1976 | 420 |
גאוגרפיה

בתחום המועצה עובר אחד מכבישי האורך החשובים במדינת ישראל: כביש 90, המהווה ציר ראשי המקשר בין דרום הארץ לצפונה.
גבולות שטח השיפוט של המועצה הם:
בדרום - העיר יריחו, השייכת לרשות הפלסטינית, וכן מועצה אזורית מגילות - בצפון ים המלח.
בצפון - מועצה אזורית עמק המעיינות
במזרח - נהר הירדן, גבול ישראל-ירדן
במערב - המורדות המזרחיים של הרי השומרון, מועצה מקומית מעלה אפרים - מועצה אזורית שומרון, מועצה אזורית מטה בנימין.
רקע היסטורי וחברתי

השטח עליו הוקמה לאחר מכן המועצה, נכבש על ידי ישראל מממלכת ירדן בשנת 1967 במהלך מלחמת ששת הימים. לאחר המלחמה הוחל בהקמת יישובים ישראליים בבקעה. ראשון היישובים היה מחולה, שהוקם בשנת 1967, ולאחריה הוקמו כיישובים אזרחיים פצאל, חמרה, ארגמן ובקעות. כן הוקמו היאחזויות נח"ל שאוזרחו לאחר מכן. תחילה קיבלו היישובים שירותים ממועצה אזורית בקעת בית שאן.
המועצה האזורית הוקמה בתחילת 1980 בצו של המושל הצבאי של צה"ל באזור יהודה ושומרון.
ממצאים ארכאולוגיים מעידים על התיישבות יהודית באזור הן בתקופת בית שני והן בתקופות מוקדמות יותר. לדוגמה, בעיר יריחו נמצאו שרידי בית כנסת עתיק.
מבחינה כלכלית חברתית סובלים יישובי המועצה האזורית ערבות הירדן מבעיות האופייניות לאזורי פריפריה המרוחקים מהמרכז: מיעוט תעסוקה לעובדים בעלי השכלה אקדמית, הגירה שלילית של צעירים, תשתיות לא מספקות בתחומי החינוך, התרבות ומחסור בתחבורה ציבורית.
כיום ישנם אזורים, בעיקר בצפון הבקעה שסובלים מטרור חקלאי של כפרים פלסטינים בעיקר מהכפרים ברדלה וכרדלה ועין אל-בידה.