Public conveyance system for shortest path nding for real road network

摘要

This article analyzes problems of determining the shortest path and optimal route amongst the given stoppages. The model of the problem is presented as a directional graph, where nodes are pickup points (termed as stoppage point in database) and crossings outside stoppage points and edges are roads among stoppage points and crossings. Each node has some information attached to it: stoppageld, stoppageName, latitude, longitude and number Of Passengers of the stop, maintenance organizations, and mark(s) of the crossing(s). All pickup points are connected by roads. These roads are considered as the edges of the graph. Edges also have information attached to it: road Id, source, destination, distance, time etc. We have selected Floyd Warshall algorithm to nd the shortest path between two stoppages. This algorithm works in two stages: in rst stage, it nds the shortest path between all stoppages, and in second stage it nds optimized route to visit some of these stoppages. The solution is displayed in the form of shortest distance and time between two locations. The program is written in java language. It uses 3 tables as input from database: nodes, vehicle details and road. This paper gives implementation outcome of Floyd Warshall algorithm to solve the all pairs shortestpath problem for directed road graph system. We have considered an example of a map of Pune.