package Ġchapter 4 . section 4 Ċ Ċ import Ġedu . pr inc et on . cs . al gs 4 . Stack Ċ import Ġextensions . format Double Ċ Ċ /** Ċ Ġ* Ġ åĬł æĿĥ æľī åĲĳ åĽ¾ æľĢ çŁŃ è·¯å¾Ħ çļĦ API Ċ Ġ*/ Ċ abstract Ġclass ĠSP ( protected Ġval Ġdig raph : ĠEdge Weighted Dig raph , Ġprotected Ġval Ġs : ĠInt ) Ġ{ ĊĠĠĠ Ġprotected Ġval Ġedge To Ġ= ĠarrayOf Null s < Direct ed Edge >( dig raph . V ) ĊĠĠĠ Ġprotected Ġval Ġdist To Ġ= ĠArray ( dig raph . V ) Ġ{ ĠDouble . POSITIVE _ INFINITY Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* Ġä»İ é¡¶ çĤ¹ s åĪ° v çļĦ è·Ŀç¦» ï¼Į å¦Ĥæŀľ ä¸įåŃĺåľ¨ åĪĻ è·¯å¾Ħ ä¸º æĹł ç© · å¤§ ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġopen Ġfun Ġdist To ( v : ĠInt ): ĠDouble Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġdist To [ v ] ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* Ġæĺ¯åĲ¦ åŃĺåľ¨ ä»İ é¡¶ çĤ¹ s åĪ° v çļĦ è·¯å¾Ħ ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġopen Ġfun Ġhas Path To ( v : ĠInt ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġdist To [ v ] Ġ!= ĠDouble . POSITIVE _ INFINITY ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* Ġä»İ é¡¶ çĤ¹ s åĪ° v çļĦ æľĢ çŁŃ è·¯å¾Ħ ï¼Į å¦Ĥæŀľ ä¸įåŃĺåľ¨ åĪĻ ä¸º null ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġopen Ġfun Ġpath To ( v : ĠInt ): ĠIterable < Direct ed Edge >? Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ(! has Path To ( v )) Ġreturn Ġnull ĊĠĠĠĠĠĠĠ Ġval Ġstack Ġ= ĠStack < Direct ed Edge >() ĊĠĠĠĠĠĠĠ Ġvar Ġedge Ġ= Ġedge To [ v ] ĊĠĠĠĠĠĠĠ Ġwhile Ġ( edge Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstack . push ( edge ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġedge Ġ= Ġedge To [ edge . from ()] ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġstack ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠ Ġval ĠstringBuilder Ġ= ĠStringBuilder () ĊĠĠĠĠĠĠĠ Ġfor Ġ( v Ġin Ġ 0 Ġuntil Ġdig raph . V ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠstringBuilder . append ( s ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. append (" Ġto Ġ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. append ( v ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( has Path To ( v )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠstringBuilder . append (" Ġ( ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. append ( format Double ( dist To ( v ), Ġ 2 )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. append (" ): ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpath To ( v ) !!. forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠstringBuilder . append (" Ġ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. append ( it . toString ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠstringBuilder . append ("\ n ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠstringBuilder . append (" ĠUn reachable \ n ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn ĠstringBuilder . toString () ĊĠĠĠ Ġ} Ċ }