부산대학교 도서관

In our approach to find a suitable means for accessing and traversing a graph with edges that have the some alternating weight assigned to them. We studied combinational properties of graphs, thus allowing us to come to a newer and easier method to fully traverse a dynamic graph that stimulates the real-time environment with the weight upon its edges changing continuously. Our approach yields a fully dynamic algorithm for general directed graphs with non-negative edges with weights that are revalued continuously. The sequence of operations remains to be in O(n2) amortized time per update and unit worst-case time per distance query, where n is the number of vertices. The focus of our study is to primarily ensure that in an environment where several nodes co-exist with weights and paths on the edges sprouting irregularly, there is still a palpable method to calculate the shortest path. Our algorithm is deterministic, uses simple data structures thus is efficient to be employed for its goal.