Iskanje najkrajših poti med točkami telekomunikacijskega omrežja : diplomsko delo

Gobov, Miha (avtor), Rožanc, Igor (mentor)

Diplomsko delo opisuje rešitev problema iskanja povezav med točkama v telekomunikacijskem omrežju. Za rešitev problema imamo na voljo podroben prostorski izris omrežja ter seznam parov začetnih in končnih koordinat, med katerimi je treba poiskati najkrajše poti. Podatki o omrežju so podani v formatu shapefile, ki je namenjen shranjevanju vektorskih podatkov v geografskih informacijskih sistemih. Da bi lahko iskali poti v podanem omrežju, smo ga pretvorili v obliko grafa. Tega smo shranili v grafno podatkovno bazo, to je namensko orodje za delo z grafi v obliki vozlišč in povezav. Začetne in končne koordinate smo nato povezali na liste v grafu. Za iskanje najkrajših poti smo uporabili Dijkstrov algoritem. Rezultat smo nato shranili v obliko CSV. Rešitev smo vizualno prikazali tudi v geografskem informacijskem sistemu, kjer smo za uvoz podatkov uporabili obliko Well-known text.

• Jezik: Slovenski jezik
• Ključne besede: prostorski podatki, grafne podatkovne baze, problem iskanja najkrajših poti, Dijkstrin argoritem iskanja najkrajših poti, računalništvo, visokošolski strokovni študij, računalništvo in informatika, diplomske naloge
• Vrsta gradiva: Diplomsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Založnik: [M. Gobov]
• Leto izida: 2014
• Št. strani: 38 str.
• PID: 20.500.12556/RUL-68681
• UDK: 004.7(043.2)
• COBISS.SI-ID: 10700372
• Datum objave v RUL: 10.07.2015

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Searching for shortest paths between nodes of telecommunication network

Izvleček

The thesis describes a solution to the shortest path problem between two points in a telecommunication network. To solve the problem a detailed spatial data describing network and the list of start and end coordinate pairs are available, between which we have to find the shortest path. The network layout is provided in the shapefile format which is used for storing vector geospatial data in geographic information systems. In order to be able to search for paths in the network, we have transformed it into a graph form. We have saved the graph into the graph database, which is a purpose tool for working with graphs in the form of vertices and edges. Start and end coordinate points were then connected to the leaves in the graph. In order to look for of the shortest paths we have used Dijkstra's algorithm. Results were then stored in the CSV format. The results were also visualised in the geographic information system, where we used the Well-known text format to import them.

• Ključne besede: spatial data, graph database, shortest path problem, Dijkstra's algorithm for finding the shortest path, computer science, computer and information science, diploma