Search for shortest paths based on the projective description of unweighted graphs

Avatar
Poster
Voice is AI-generated
Connected to paperThis paper is a preprint and has not been certified by peer review

Shortest paths search method based on the projective description of unweighted mixed graphs

Authors

V. A. Melent'ev

Abstract

The method is based on the preliminary transformation of the traditionally used matrices or adjacency lists in the graph theory into refined projections free from redundant information, and their subsequent use in constructing shortest paths. Unlike adjacency matrices and lists based on enumerating binary adjacency relations, the refined projection is based on enumerating more complex relations: simple paths from a given graph vertex that are shortest. The preliminary acquisition of such projections reduces the algorithmic complexity of applications using them and improves their volumetric and real-time characteristics to linear ones for a pair of vertices. The class of graphs considered is extended to mixed graphs.

Follow Us on

0 comments

Add comment