MODIFICATION OF DIJKSTRA'S ALGORITHM TO DETERMINE THE DATABASE OF OPTIMAL ROUTES IN THE TRANSPORT NETWORK
TSITSIASHVILI G.SH. IAM FEB RAS, Gurami Sh. Tsitsiashvili, A.N. GAVRILOV · Informatika i sistemy upravleniya · 2025
The problem of determining the shortest paths in a finite weighted digraph from the initial vertex to the remaining vertices of the graph is considered. This problem is solving by introducing into Dijkstra's algorithm lists of labels characterizing the vertices from which the edges of the shortest paths enter the vertices of the graph. Such lists of labels form a database for determining the shortest paths in the digraph. Using this procedure, the problems of increasing or decreasing the list of labels due to variations in the edge lengths of a weighted graph are considering. In particular, the problem of removing unwanted edges from a through transportation route is solved.