package Ġcom . android app . nav wei android v 2 . presentation . location details . map tab . di jk stra ĊĊ Ċ import Ġandroid . util . Log Ċ import Ġjava . lang .* Ċ Ċ /** Ċ Ġ* ĠCreated Ġby ĠS . N ur ĠU ys al Ġon Ġ 2 0 1 9 - 1 2 - 2 3 . Ċ Ġ*/ ĊĊĊĊ Ċ class ĠD ijk stra ( graph : ĠDW Graph , Ġval Ġfrom Index : ĠInt ) Ġ{ ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* Ġdist To [ v ] Ġ= Ġdistance Ġ Ġof Ġshortest Ġs -> v Ġpath ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġval Ġdist To : ĠDouble Array Ġ= ĠDouble Array ( graph . V , Ġ{ Ġif Ġ( it Ġ== Ġfrom Index ) Ġ 0 . 0 Ġelse ĠDouble . POSITIVE _ INFINITY Ġ}) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* Ġedge To [ v ] Ġ= Ġlast Ġedge Ġon Ġshortest Ġs -> v Ġpath ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġval Ġedge To : ĠArray < DW Graph . Edge ?> Ġ= ĠarrayOf Null s ( graph . V ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* Ġpriority Ġqueue Ġof Ġvertices ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġval Ġpq : ĠIndexed Priority Queue < Double > Ġ= ĊĠĠĠĠĠĠĠ ĠIndexed Priority Queue ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġgraph . V ĊĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( graph . edges (). any Ġ{ Ġit . weight Ġ< Ġ 0 Ġ}) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthrow ĠIllegalArgumentException (" there Ġis Ġa Ġnegative Ġweight Ġedge ") ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// Ġrelax Ġvertices Ġin Ġorder Ġof Ġdistance Ġfr hom Ġs ĊĠĠĠĠĠĠĠ Ġpq . insert ( from Index , Ġdist To [ from Index ]) ĊĠĠĠĠĠĠĠ Ġwhile Ġ(! pq . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġv Ġ= Ġpq . poll (). first ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( e Ġin Ġgraph . adjacent Edges ( v )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrelax ( e ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// Ġrelax Ġedge Ġe Ġand Ġupdate Ġpq Ġif Ġchanged ĊĠĠĠ Ġprivate Ġfun Ġrelax ( e : ĠDW Graph . Edge ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġfrom Ġ= Ġe . from Index ĊĠĠĠĠĠĠĠ Ġval Ġto Ġ= Ġe . to Index ĊĠĠĠĠĠĠĠ Ġif Ġ( dist To [ to ] Ġ> Ġdist To [ from ] Ġ+ Ġe . weight ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdist To [ to ] Ġ= Ġdist To [ from ] Ġ+ Ġe . weight ĊĠĠĠĠĠĠĠĠĠĠĠ Ġedge To [ to ] Ġ= Ġe ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( pq . contains ( to )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpq . decrease Key ( to , Ġdist To [ to ]) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpq . insert ( to , Ġdist To [ to ]) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġthe Ġlength Ġof Ġa Ġshortest Ġpath Ġfrom Ġthe Ġsource Ġvertex Ġ` s ` Ġto Ġvertex Ġ` v `. ĊĠĠĠĠ Ġ* Ġ@ param Ġ Ġv Ġthe Ġdestination Ġvertex ĊĠĠĠĠ Ġ* Ġ@ return Ġthe Ġlength Ġof Ġa Ġshortest Ġpath Ġfrom Ġthe Ġsource Ġvertex Ġ` s ` Ġto Ġvertex Ġ` v `; ĊĠĠĠĠ Ġ* ĠĠĠĠĠĠĠĠ Ġ` Double . POSITIVE _ INFINITY ` Ġif Ġno Ġsuch Ġpath ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġdist To ( v : ĠInt ): ĠDouble Ġ{ ĊĠĠĠĠĠĠĠ ĠLog . d (" MAP ", Ġ" dist To [ v ]: ${ dist To [ v ]} Ġ") ĊĊĠĠĠĠĠĠĠ Ġreturn Ġdist To [ v ] ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġtrue Ġif Ġthere Ġis Ġa Ġpath Ġfrom Ġthe Ġsource Ġvertex Ġ` s ` Ġto Ġvertex Ġ` v `. ĊĠĠĠĠ Ġ* Ġ@ param Ġ Ġv Ġthe Ġdestination Ġvertex ĊĠĠĠĠ Ġ* Ġ@ return Ġ` true ` Ġif Ġthere Ġis Ġa Ġpath Ġfrom Ġthe Ġsource Ġvertex ĊĠĠĠĠ Ġ* ĠĠĠĠĠĠĠĠ Ġ` s ` Ġto Ġvertex Ġ` v `; Ġ` false ` Ġotherwise ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġhas Path To ( v : ĠInt ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġdist To [ v ] Ġ< Ġjava . lang . Double . POSITIVE _ INFINITY ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġa Ġshortest Ġpath Ġfrom Ġthe Ġsource Ġvertex Ġ` s ` Ġto Ġvertex Ġ` v `. ĊĠĠĠĠ Ġ* Ġ@ param Ġ Ġv Ġthe Ġdestination Ġvertex ĊĠĠĠĠ Ġ* Ġ@ return Ġa Ġshortest Ġpath Ġfrom Ġthe Ġsource Ġvertex Ġ` s ` Ġto Ġvertex Ġ` v ` ĊĠĠĠĠ Ġ* ĠĠĠĠĠĠĠĠ Ġas Ġan Ġiterable Ġof Ġedges , Ġand Ġ` null ` Ġif Ġno Ġsuch Ġpath ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġpath To ( v : ĠInt ): ĠIterable < DW Graph . Edge > Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ(! has Path To ( v )) Ġthrow ĠNoSuch Path Exception ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ" There Ġis Ġno Ġpath Ġfrom Ġ[$ from Index ] Ġto Ġ[$ v ]" ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġval Ġpath Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠ ĠStack < DW Graph . Edge >() ĊĠĠĠĠĠĠĠ Ġvar Ġe Ġ= Ġedge To [ v ] ĊĠĠĠĠĠĠĠ Ġwhile Ġ( e Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpath . push ( e ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġe Ġ= Ġedge To [ e . from Index ] ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġpath ĊĠĠĠ Ġ} Ċ }