Shortest Route Algorithm Using Fuzzy Graph
G. Nirmala, K. Uma · 2013
The current widespread use of location-based services and Global Positioning System technologies has revived interest in very fast and scalable fuzzy shortest path queries. We introduce a new shortest path query type in which dynamic constraints may be placed on the allowable set of edges that can appear on a valid fuzzy shortest path (e.g., dynamically restricting the type of roads or modes of travel which may be considered in a multimodal transportation network). Computing the shortest path between two given locations in a road network is an important problem that finds applications in various map services and commercial navigation products. Our experimental results reveal the characteristics of different techniques ,based on which we provide guidelines on selecting appropriate methods for various scenarios. Although the raw data about geography and roads may be more readily available today, computing fuzzy shortest paths is still not trivial. kruskal's algorithm allows us to compute point-to-point fuzzy shortest path queries on any road network in essentially linear time. . In a preprocessing stage, these heuristics compute some auxiliary data, such as additional edges (shortcuts) and labels or values associated with vertices or edges.