על כן, האלגוריתם "מתקן" את המשקלים בדרך הבאה: הוא מגדיר פונקציה formula_1 שמתאימה לכל צומת מספר ממשי, ואז מתקנת באמצעותה את המשקל של כל קשת. אם משקל הקשת formula_2 היה formula_3, היא מגדירה משקל חדש formula_4. ניתן להראות ששינוי זה של המשקלים לא משנה את התכונה המהותית שנחוצה בגרף - כל מסלול קל ביותר בגרף המקורי הוא קל ביותר גם בגרף החדש (תכונה זו אינה נשמרת אם מגדילים את משקלי כל הקשתות במספר קבוע אחד לכולן, למשל).
כדי למצוא פונקציה formula_5 שתבטיח שהמשקלים בגרף החדש יהיו כולם חיוביים, אלגוריתם ג'ונסון משתמש באלגוריתם בלמן-פורד בדרך הבאה: ראשית הוא מוסיף לגרף המקורי צומת חדש formula_6 ומוסיף קשת במשקל 0 מ-formula_6 אל כל formula_8. כעת הוא מריץ את אלגוריתם בלמן פורד על הצומת formula_6. אם האלגוריתם מתריע על מעגל שלילי, אלגוריתם ג'ונסון מודיע זאת ומפסיק. אחרת, הוא משתמש בתוצאת אלגוריתם בלמן פורד כדי להגדיר את הפונקציה formula_5 כך: formula_11 כאשר formula_12 הוא משקל המסלול הקל ביותר מ-formula_6 אל formula_14. לאחר תיקון המשקלות בגרף המקורי מריץ אלגוריתם ג'ונסון את אלגוריתם דייקסטרה על כל הצמתים, כמתואר לעיל.
סיבוכיות זמן.
כיוון שסיבוכיות הזמן של אלגוריתם דייקסטרה היא formula_15 במימוש האופטימלי שלו, והאלגוריתם מורץ formula_16 פעמים (פעם אחת לכל אחד מהצמתים), סיבוכיות הזמן של חלק זה של האלגוריתם היא formula_17. סיבוכיות בלמן פורד היא formula_18 ומכיוון שהוא מורץ רק פעם אחת הוא אינו משפיע על זמן ריצת האלגוריתם.
כאשר הגרף דליל, כלומר מבחינה פורמלית מתקיים formula_19, סיבוכיות האלגוריתם של ג'ונסון תהיה נמוכה מ-formula_20, שהיא הסיבוכיות של אלגוריתמים אחרים לפתרון בעיית המסלולים הקצרים ביותר בין כל שני זוגות צמתים, דוגמת האלגוריתם של פלויד-וורשאל.
עיצורים צידיים
עיצורים צידיים הם עיצורים שבמהלך הפקתם האוויר משתחרר מציד אחד או משני צידי הלשון כאשר לרוב נוצר קשר בין קצה הלשון לבין השיניים העליונות או בין הלשון למכתש, בשונה משאר העיצורים שהם מרכזיים ובהם האוויר משתחרר מעל מרכז הלשון. רוב העיצורים הצידיים הם עיצורים מקורבים מקבוצת העיצורים הנזילים, חלקם עיצורים חוככים מקבוצת העיצורים החוככים הבלתי שורקים, עיצור צידי אחד הוא עיצור מקיש מקבוצת העיצורים המקישים צידיים ועיצור צידי נוסף הוא עיצור מצוץ מקבוצת העיצורים המצוצים צידיים. כאשר מופיעים בטבלה שני עיצורים באותה משבצת, העיצור הימני קולי והשמאלי אטום.
סומטרה
סומטרה הוא האי השישי בגודלו בעולם וחלק מאינדונזיה.
אטימולוגיה.
בעבר הרחוק קראו ההודים לאי בשם "סוארנאם דויפא" שמשמעו בסנסקריט "אי הזהב" בהיפוך סדר המילים.
בשנת 1267 נוסדה על חופו הצפוני של האי עיר-מדינה בשם SAMUDERA PASAI העיר שלטה על גזרה קטנה בצורת חצי עגול בחוף הצפוני. משמעות השם SAMUDERA וגם SAMUDRA במאלאית/אינדונזית היא "אוקיינוס". העיר הייתה מראשיתה בשלטון מוסלמי, וסוחרים ערביים שסחרו אתה שבשו את שמה ל سومطرة "סומטרה" הקרי הנחצי של האות ط טאא ערבית המקבילה לאות ט בעברית, גרם לדייקני המעתיקים שלא כתבו באותיות ערביות לכתוב SUMATERA עם E באמצע. קצרנות, אפילו מקומית, ושבוש זר גרמו לאירופים לכתוב SUMATRA במפותיהם. הכתיב הרשמי SUMATERA אומץ על ידי האינדונזים ונקבע בחוק על ידי הנשיא סוקרנו בשנת 1954.
שם נוסף לסומטרה הוא "אנדאלאס" (Andalas), שהוא גם שמו של עץ בגובה 35 מטרים.
גאוגרפיה וטבע.
האי סומטרה משתרע על 443,065.8 קילומטר רבוע (שטח מעט קטן יותר משוודיה). הוא האי השלישי בגודלו בארכיפלג המלאי והאי הגדול ביותר שכולו שייך לאינדונזיה.
ניתן לחלק את סומטרה חלוקה גסה לשני אזורים גאוגרפיים מרכזיים: האזור ההררי לחופו המערבי של האי ולשפלה בוצית ממזרחו.
בעבר היה סומטרה מכוסה ברובה יער גשם טרופי אך הפיתוח הכלכלי וכן כריתת-יערות בלתי-חוקית גבו מחיר כבד על החי והצומח באי. בין החיות שניתן למצוא על האי נמנים האורנגאוטן, הטיגריס הסומטרי (הייחודי לאי), פיל סומטרי, קרנף סומטרה והטפיר המלאי, כולם בסכנת הכחדה. כוח המים נפוץ באי. בסומטרה מספרים שיצורים אגדתיים כמו אורנג פנדק מסתובבים באי, והחוקרים חושבים כי מדובר באדם קדמון שמאובניו ידועים מהאי פלורס שנקרא "הומו פלורסיינסיס". מהצמחים המוכרים באי הוא רפלסיה, אשר ידוע משום שהוא מצמיח את פרח הגדול ביותר בעולם וכמו כן מפיץ ריח רע המזכיר ריח בשר נרקב.
בשנת 2004, בעקבות תזוזת לוחות טקטוניים באזור סומטרה, התרחשה רעידת אדמה שגרמה לצונמי. רעידה חזקה נוספת התרחשה ב-2005. רעידת האדמה שהתרחשה ב-2009 גרמה למותם של אלפי בני אדם והרס עשרות אלפי מבנים. באפריל 2010 התרחשה באי רעידת אדמה נוספת בעוצמה של 7.7 בסולם ריכטר שגרמה להרס רב של מבנים ובתי מגורים רבים, אך רק 12 בני אדם מצאו את מותם ברעידת האדמה.
ב-29 באוגוסט 2010 התפרץ הר הגעש סינבונג, הנמצא בצפון סומטרה, אשר התפרץ בפעם האחרונה בשנת 1600. בעקבות ההתפרצות פונו 10,000 תושבים
אוכלוסייה.
בסומטרה חיים כ-20% מתושבי המדינה, כ-42 מיליון איש. צפיפות האוכלוסין בסומטרה היא 85 איש לקמ"ר (לעומת 864 איש לקמ"ר בג'אווה). הערים הגדולות באי הן (עם אוכלוסייתן בשנת 2000) מדן (קרי במאלאית "מידאן": "מקום מפגש", "ככר"), (1,703,885), פלמבנג (1,194,440), פאדאנג ("מישור") (705,044), טנג'ונגקרנג-טלוקבטונג (670,074) ופקאנבארו ("שוק חדש") (528,679).
היסטוריה.
מעטים ישבו באי בפרהיסטוריה. לפני כ-75,000 שנה נמחו כמעט כל תושבי האי בהתפרצות געשית אדירה שיצרה את אגם טובה. בני הגזע המאלאי הגיעו אל אינדונזיה בשני גלים. הראשון החל מ-2500 לפנה"ס, השני החל מ-1500 לפנה"ס. לפי האנציקלופדיה של האסלאם מקור השפה המאלאית כנראה באי סומטרה. סוחרים מהודו הגיעו לאי, יש אומרים החל משנת 78 לספירה מועד ראשית מנין שנות אג'י סאכא, ויש אומרים החל משנת 101 והפיצו שם את הבודהיזם ויותר מאוחר את ההינדואיזם. ההודים כנו את האי סומטרה בשם "סוארנאם דויפא" שמשמעו בסנסקריט "אי הזהב".
בשנת 671 נוסדה ממלכת סריוויג'יה בעיר פלמבאנג. עדות ראשונה משם הביא הסיני אי טסינג. הכתובת העתיקה ביותר בשפה המאלאית כתובת כדוכאן בוכית מעידה על סריוויג'יה וזמנה מיום 16 ביוני 682. הממלכה שלטה בשיאה על מאלאיה וסומטרה ומסחרה הגיע עד אל הפיליפינים. רוב אוכלוסיית האי קיבלה את האסלאם, שצץ באי בשנת 48 להג'רה, היא 668 / 669 לספירת הנוצרים. מצבת קבר ערבית נמצאה בבארוס ותאריכה מאותה שנה. על פי עדותו של נוסע סיני הוא פגש מוסלמים באי בשנת 674 לספירת הנוצרים.
בסומטרה נמצאה כתובת כדוכאן בוכית, מתוארכת לשנת 682, והיא הכתובת העתיקה ביותר בשפה המאלאית.
ממלכת סריויג'איא יצרה קשר עם הח'ליפה עמר בן עבד אלעזיז החל משנת 100 להג'רה 718 לספירה הנוצרית. אז שלח המאהאראג'א סרי אינדראוארמאן של סריויג'איא מכתב אל הח'ליפה בבקשה שישלח אליו מטיף ללמדו את האסלאם. אין בזה אשור לאסלום ממלכת סריויג'איא כי נתיניה המשיכו להאמין בבודהיזם. תשובת המוסלמים למכתב באה במכתב משנת 724 לספירת הנוצרים בלווי שפחה "זנג'ית" אפריקנית שחורה שנשלחה אל סרי אינדראוארמאן. מסחרה של סריויג'איא הגיע עד מדגסקר במערב, כולל מהגרים מסריויג'איא שנותרו שם בשנת 830 לספירה הנוצרית, הודו, תאילנד, הפיליפינים, מלאיה, סין וכל מרחבי הארכיפלג האינדונזי עד אל מערב גינאה החדשה. ישנה כתובת חרוטה על לוח נחושת שנמצאה בפיליפינים המעידה על קשר בין הפיליפינים לסריויג'איא והאי ג'אווה. הכתובת מכילה מילים מ 4 שפות: סנסקריט, מלאית עתיקה, טגלוג ושפת האי ג'אווה. זמנה מקביל ליום שני 21 באפריל שנת 900 לספירה הנוצרית. בשנת 1292 ביקר מרקו פולו בפאסאי הוא הזכיר שמוסלמים חיים לאורך החוף ובפנים האי פראים. בשנת 1346 בקר באי אבן בטוטה. בסביבות 1400 השלימה ממלכת מאג'אפאהית את כיבוש כל שטח סריוויג'יה. בשנת 1478 השלימו המוסלמים את כבוש כל חופי האי מממלכת מאג'אפאהית. בשנת 1496 כבר התקיימה סולטנות אצ'ה בצפון האי.
בשנת 1505 הופיעו הפורטוגזים לראשונה באינדונזיה. בשנת 1521 כבשו הפורטוגזים את פאסאי. שליטי אצ'ה כרתו ברית עם האימפריה העות'מאנית בשנת 1530. בשנת 1585 שלח סולטאן אצ'ה מכתב אל אליזבת הראשונה מלכת אנגליה בבקשו עזרה במלחמתו בפורטוגלים. המכתב היה מנוסח במאלאית קלאסית בכתב ג'אווי וכלל גם מילים שאינן נפוצות בדיבור בימינו.
בשנת 1599 הופיעו ההולנדים לראשונה באי והסתבכו בקרב שבו נהרג מפקדם קורנליס דה הותמאן. בשנת 1664 הצליחו ההולנדים לסלק את הפורטוגזים מהאי. בשנת 1685 נאחזו גם הבריטים באי. העיר בנגקולו הייתה בשליטתם ועוד מאחז אחד לפחות שמקומו לא ברור. בשנת 1821 פרצה מלחמת פאדרי שבה החלה הולנד לכבוש את האי החל מן הדרום. בשנת 1823 כבשו ההולנדים את סולטנות פלמבנג. המלחמה הסתימה בשנת 1837 בכבוש אזור מגורי מינאנגקבאו.