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

Gobov, Miha (author), 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.

• Language: Slovenian
• Keywords: 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
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Publisher: [M. Gobov]
• Year: 2014
• Number of pages: 38 str.
• PID: 20.500.12556/RUL-68681
• UDC: 004.7(043.2)
• COBISS.SI-ID: 10700372
• Publication date in RUL: 10.07.2015

Secondary language

• Language: English
• Title: Searching for shortest paths between nodes of telecommunication network

Abstract

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.

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