Best route calculation algorithm

Question

I’m doing a logging system that addresses the issue of routes/routing. Where I should choose the best route to travel.

Initially I am only doing some tests and testing advanced algorithms, what I am doing seems to be something illogical, but it will meet my need.

Come on, let’s go: I have a bank of registered locations. These locations can make borders with several other locations. For each location is informed the distance in KM.

Based on the registered locations, the system has an option in which the user informs two points (origin and destination) and at the end the system informs the route for the vehicle to reach its given destination considering the shortest way.

I already have some cities, for example, Cidadea, Cidadeb, Cidadec, Cidaded, cidadee.

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 the cityA to cityeB, so he has to bring me all the routes, that is, all the tickets to get to the city D in the most "fast" way, by the distance, then he has to bring the points, so

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

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

I tried to cross joins and analyze, I tried to give go inside until I find, but it’s something that seems infinite, even thinking too much becomes difficult to assemble. Does anyone know a way, famous algorithms that do this? I’m checking out the A* algorithms, etc, but they still haven’t helped me.

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

    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

Answer 1

This is a problem of minimum path, unidirectional believe (the distance from A to B is the same distance from B to A) and no negative weight (the 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/unsubscribed, it may be worth using an algorithm that calculates the shortest paths between all pairs. So all you need to do is consult the result, quickly, without having to recalculate it.

There are several applicable algorithms, each with characteristics specific to the level of complexity [asymptotic], domain restrictions, etc., choose one that meets your particular needs. In the absence of specific requirements, dijkstra’s 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 a ready implementation) outside the bank, in the same application layer. If you want to do everything in the bank, there is an implementation route stored Procedure (MS SQL CLR) which 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 columns (cidade, valor, anterior, visitado). Initially, fill this table with your cities, marking them all as "not visited", the former as null and the value as "infinite" (or simply a very large number). Then perform the following steps:

1. Mark the initial city value as zero (because the distance from A to A is zero);
2. While your destination [or all cities] has not yet been visited, do:
   1. Select the city X not visited with the lowest value;
   2. Select All Cities Y not visited that are adjacent to it (i.e. reachable from it);
   3. Add up the distance between X and Y with the value of X, and compare with the value of Y; if it is smaller, update the value of Y and the countryside anterior of Y;
   4. Mark the city X as "visited".

At the end, you will have for each city a value corresponding to the minimum distance between A and her, and a anterior telling from which city one arrives at it by walking that distance. To find the exact path, start from B and follow the anterior until you get into A.

Answer 2

From what I understand, you have the shortest path problem and then you can use the algorithm of Dijkstra to find the optimal solution in polynomial time. To implement, the ideal would be to get the city list and its distances from the database and assemble a data structure to run the algorithm and not try to run it directly in the BD.