Best Route Calculation Algorithm

Question

Best Route Calculation Algorithm

Navigation

#1 by (6 votes)
#2 by (4 votes)

9

I'm doing a logic system that addresses the route / routing issue. Where should I choose the best route to travel.

Initially I'm just doing some testing and testing advanced algorithms, what I'm doing seems like something illogical, but it will suit my need.

Come on: I have a bank of registered sites. These locations can border with several other locations. For each locality the distance is reported in KM.

Based on the registered locations, the system has an option where the user informs two points (origin and destination) and at the end the system informs the route so that the vehicle arrives at its destination considering the shortest path. / p>

I already have some cities, for example, CityA, CityB, CityC, CityD, cityE.

For example,

de CidadeA pra cidadeB são 5 km.
de CidadeB para cidadeC são 7 km.
de CidadeC para cidadeE são 22 km.
de CidadeC para cidadeD são 8 km.
e assim como posso ter outras cidades.

And I chose (two comboboxes) to go from city to cityB, so he should bring me all the routes, that is, all the passes to get to city D in the fastest way, by the distance, there he should bring the points, so

CidadeA - > CidadeB
CidadeB - > Cidade C...
e assim sucessivamente.

The user informs the source and destination, the system must calculate showing point by point where it should pass.

I tried to do cross joins and analyze, I tried to give inside for until finding, but it is something that seems infinite, even thinking a lot is difficult to assemble. Does anyone know a way, famous algorithms that do this? I'm checking the A * algorithm, etc., but it still has not helped.

Friends, here is the structure of the tables: Location table and the DistanceLocations table.

    use master
go
CREATE DATABASE Rota
go
USE Rota
GO

CREATE TABLE [dbo].[Localidade](
    [cod_cidade] [int] IDENTITY(1,1) NOT NULL,
    [nome] [varchar](50) NULL,
 CONSTRAINT [PK_Localidade] PRIMARY KEY CLUSTERED 
(
    [cod_cidade] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]

GO

SET ANSI_PADDING OFF
GO


CREATE TABLE [dbo].[DistanciaCidades](
    [cod_cidade1] [int] NOT NULL,
    [cod_cidade2] [int] NOT NULL,
    [distancia] [int] NULL,
 CONSTRAINT [PK_DistanciaCidades] PRIMARY KEY CLUSTERED 
(
    [cod_cidade1] ASC,
    [cod_cidade2] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]

GO

c#

asked by anonymous 30.12.2014 / 01:53

2 answers

What data types exist in MySQL for texts? How to hide the source code of the PHP file?

score 6 · Answer 1

This is a problem of minimum path , one way I believe (the distance from A to B is the same distance from B to A) and without negative weights (distance is always greater than or equal to zero). Considering that the distance between cities does not change frequently (except for the opening of new roads, etc.) and that cities are not commonly registered / descadastradas, it is worthwhile to use an algorithm that calculates the shortest paths between all the pairs. So all you need to do is query the result quickly without having to recalculate it.

There are several applicable algorithms , each with specific characteristics regarding the level of complexity [asymptotic] , domain restrictions, etc., choose one that suits your particular needs. In the absence of specific requirements, the Dijkstra algorithm seems to be the simplest and most efficient, at least for the most common applications.

My first suggestion is to implement (or search for an implementation already ready ) off the bank, at the same application layer. If you want to do everything in the database, an stored procedure (MS SQL CLR) that may be of interest to you. In the rest of this answer, I will outline how to implement by hand, not necessarily in the best or most efficient way, okay?

A simple implementation would consist of the following: Create a temporary table, with the columns ( cidade, valor, anterior, visitado) . Initially, fill this table with your cities, marking them all as "unvisited", the previous one as null and the value as "infinite "(or simply a very large number). Then perform the following steps:

Mark the starting city value as zero (because the distance from A to A is zero);

While your destination [or all cities] has not yet been visited, do:

Select the city X not visited with the lowest value;

Select all the% uncached% cities that are adjacent to it (i.e. reachable from it);

Add the distance between Y and X to the value of Y , and compare with the value of X ; if it is smaller, update the value of Y and the field Y of anterior ;

Mark% city as% visited as "visited."

At the end you will have for each city a value corresponding to the minimum distance between Y and it, and a X saying from which city you arrive at it traveling that distance. To find the exact path, start from A and follow anterior to reach B .

score 4 · Answer 2

As I understand it, you have the shortest path problem and you can use the algorithm of < strong> Dijkstra to find the optimal solution in polynomial time. To implement, the ideal would be to get the list of city and its distances from the database and to assemble a data structure to run the algorithm and not try to run this direct in the DB.