PDF Publication Title:
Text from PDF Page: 033
Route Planning Floyd-Warshall Algorithm Let’s define that the vertices represent the charging stations and the edges are paths be- tween them. The edges are in this route planning problem oriented. There has to be considered that the path from A to B can be quite different than path from B to A al- though there is the same road and yet the existence of edge between A and B does not imply edge between B and A as well. The duration can be often different. The graph with oriented edges is called as directed graph [Hlinˇeny ́, 2010]. 6.3.1 Path in Directed Graphs Path in directed graph is a sequence of vertices defined as P = (v1, ..., vn) and it begins from vertexv1 ∈V tovertexvn ∈V. Thereexistanedgesei =(vi,vi+1)∈Efori=1,...,n−1. This path is defined by start and destination vertices and tuple of vertices between them with oriented edges [Hlinˇeny ́, 2010]. 6.3.2 The Shortest Path The problem in route planning leads to the shortest path problem. It is about getting from origin to the destination with the shortest path across necessary count of charging stations. The attention is focused on the minimum value of the duration of all possible paths. There are two approaches of shortest path problem used in this thesis: 6.4 The All-Pairs Shortest Path problem. It finds shortest path between all vertices in our graph. (Floyd-Warshall algorithm) The Single-Pair Shortest Path problem. It finds shortest path between given vertices in our graph. (Dijkstra algorithm) Floyd-Warshall Algorithm Floyd-Warshall algorithm is an algorithm based on dynamic programming [Kola ́ˇr, 2004]. It was first approach I used in route planning in this thesis. It is simple to implement it in Java at the expense of its asymptotic complexity which is O(|N3|), where |N| is number of vertices in the graph. Java implementation of an algorithm: /** 25PDF Image | Driving Range Estimation and Trajectory Planning
PDF Search Title:
Driving Range Estimation and Trajectory PlanningOriginal File Name Searched:
Diplomka.pdfDIY PDF Search: Google It | Yahoo | Bing
Cruise Ship Reviews | Luxury Resort | Jet | Yacht | and Travel Tech More Info
Cruising Review Topics and Articles More Info
Software based on Filemaker for the travel industry More Info
The Burgenstock Resort: Reviews on CruisingReview website... More Info
Resort Reviews: World Class resorts... More Info
The Riffelalp Resort: Reviews on CruisingReview website... More Info
CONTACT TEL: 608-238-6001 Email: greg@cruisingreview.com (Standard Web Page)