Kot vas veliko že ve, sem se v prvem semestru ubadal z seminarsko nalogo za algoritme in podatkovne strukture, kjer sem preračunaval najkrajše poti po LPP omrežju. Nastala je aplikacija, ki zmore izpis najkrajših poti po:

-najmanj prestopanjih

-najmanj kilometrih

-najkrajšem času

Zadeva je bila prav zanimiva, čeprav je prihajalo do raznih problemov. tukaj je par slikic:

1.     Navodila za uporabo

Za uporabo potrebujete povprečno zmogljiv računalnik (Athlon 64 ali močnejši, najmanj 1GB RAM za windows vista), operacijski sistem, ki podpira Java virtual machine in Java virtual machine(z implementacij Java 1.6 ali novejše).

Program ne potrebuje nobene zunanje povezave, potrebuje pa dodane txt datoteke, ki se nahajajo v direktoriju programa. Brez sledečih program ne bo deloval.

Vmesnik

                Pri zagonu programa se najprej odpre osnovno okno.

Slika 2: osnovno okno programa.

Na sliki so v levem stolpcu vidni trije načini iskanja po grafu LPP. Prvi izpiše pot, katera vsebuje najmanj prestopanj, druga izpiše pot, ki jo avtobus prevozi od začetne do končne postaje, tretja pa izračuna pot, pri kateri potrebujemo najmanj časa za prihod na cilj ob določeni uri.

Na sredini so trije prostori za vpis začetnega in končnega postajališča ter časa prihoda na postajo. V polje za prihod na postajo lahko vpišemo poljuben čas v formatu, kjer so ure in minute prihoda ločene z dvopičjem(»:«). Polji za začetno in končno postajo sta namenjeni le izpisu ID številke začetnega oz. končnega postajališča, med tem ko lahko izbiramo proge po imenih na oknu, ki se odpre, ko kliknemo na gumb »izberi začetno postajo« oz. »izberi končno postajo«.

Slika 3: izbira začetne in končne postaje.

Ko imamo izbrano začetno in končno postajo lahko začnemo z uporabo prvih dveh načinov iskanja. Za tretji način vpišemo še uro – če polja ne spreminjamo, bo program preračunaval s časom »9:00«.

Iskanje z najmanj prestopanji

To iskanje je namenjeno najhitrejšemu prihodu na cilj, pri tem, da čim manjkrat prestopimo. Ko izberemo začetno in končno postajo, se prikaže graf, ki izriše pot, na desni strani pa se v posebnem oknu izpiše pot, katero lahko skopiramo v opomnik, na mobitel ali drugam.

Slika 4: Zemljevid Ljubljane – Pomanjšana karta, original v merilu 1 : 50000. Modre pike na zemljevidu so postajališča, z rumeno pa so napisane njihove ID številke. Z velikimi zelenimi krogi so označene postaje, čez katere potujemo.

Slabost tega sistema je neke vrste napaka v mojem algoritmu, ki ne izbira poti po vseh postajah, temveč vzame prvo progo, ki gre čez začetno postajališče in se pelje kolikor dolgo se lahko, nato prestopi na naslednje, ki ga prvega najde in tako dalje.

Iskanje z najmanj kilometri

Podobno kot pri prejšnjemu iskanju, tudi pri tem izberemo začetno in končno postajo.  Prednost pri tej izbiri je, da so razdalje med postajami najkrajše možne. Torej naredimo najkrajšo(relativno – z evklidsko razdaljo med postajališči) pot.

Slabosti: Ta algoritem izriše pot ki je večinoma identična prvemu iskanju – kar je popolnoma logično, saj so proge v relativno majhnem mestu razpršene v različne smeri. Edini do sedaj znani primeri se dogajajo v središču, kjer je preplet prog daleč največji.

Spodnji primer pojasnjuje situacijo:

Sliki 5 in 6: Iz razlike na slikah je evidentno, da zgornja slika opisuje iskanje po najmanj kilometrih, med tem ko spodnja opisuje prvi način iskanja(manj prestopanj). Postajališče pri Metalki je tako bližje kakor pri glavni pošti.

Časovno iskanje

Pri časovnem iskanju je najpomembnejši faktor čas prihodov avtobusov na postajališča. Na podlagi tega izračunamo najkrajšo pot in tudi sam čas vožnje. Prednost je v večji natančnosti rezultata.

Izpis je sledeč:

Slika 7: izpis potovanja in časa potovanja pri tretjem načinu.