Route Planning - shortest path

[Serge.potoczny]

Bonjour, J'ai regardé avec attention votre proposition d’utilisation de l'algorithme Dijkstra, et je me demande si il est possible de la faire fonctionner différemment. Plutôt que de travailler avec des sommets + liens avec longueurs, serait -il possible d'utiliser une table de segments avec leur longueur et une table de lien.
si l'on fait un parallèle avec un itinéraire on retrouve les routes d'un point à un autre et pas le villes
Merci d'avance,

 

[MajP]

Hello, I have looked carefully at your proposal to use the Dijkstra algorithm, and I wonder if it is possible to make it work differently.
Rather than working in vertices + weighted links, would it be possible to have a table of segments with their length and a link table. if we make a parallel with a route we find the roads from one point to another and not the cities
Thank you in advance,

I think your data is the same, but I am not certain. For example if the question is how to get the shortest route from Troncons 68 to Troncons 94? If so the data shows the route is 68 to 73 to 94 with a distance of 2200 + 4750 = 6950. With a path of CLP0UA_+0S18002 to CLP0UA_+0S18003. Is this what you want to do? If so the data can be used directly as is.

Je pense que vos données sont les mêmes, mais je ne suis pas certain. Par exemple, si la question est de savoir comment obtenir le trajet le plus court de Troncons 68 à Troncons 94? Si c'est le cas, les données montrent que l'itinéraire est de 68 à 73 à 94 avec une distance de 2200 + 4750 = 6950. Avec un chemin de CLP0UA_ + 0S18002 à CLP0UA_ + 0S18003. C'est ça que tu veux faire? Si tel est le cas, les données peuvent être utilisées directement telles quelles.

troncons troncons_tenant repere troncon longueur
68 69 CLP0UA_+0S18002 2200
68 73 CLP0UA_+0S18002 2200
73 94 CLP0UA_+0S18003 4750

 

[Serge.potoczny]

Merci pour ce retour rapide, j'en déduit qu'il suffit de considérer les troncons comme des sommets (tblVertices) et de faire une table de liaison entre les troncons en comptant la somme des 2 longueurs de chaque troncon (tblEdges). j'ai une difficulté cependant car les troncons sont considérés dans les 2 sens, est il possible de modifier l’algorithme ou dois-je dédoubler la table (68 69 = 2200 + 1000 , 69 68 = 1000 + 2200) ce qui aura pour inconvénient d'alourdir les tables

 

[arnelgp]

please test!

 

[Serge.potoczny]

Bonjour, merci pour cette proposition, il y a une petite erreur dans la mesure ou la jointure de la requette Query1 n'est pas bonne
Mais cela va me servir, il me semble que votre fichier prévoit le routage dans les 2 sens, est ce exact ?

 

[MajP]

I deduce that it suffices to consider the sections as vertices (tblVertices) and to make a connection table between the sections by counting the sum of the 2 lengths of each section (tblEdges). I have a difficulty however because the sections are considered in both directions, is it possible to modify the algorithm or do I have to split the table (68 69 = 2200 + 1000, 69 68 = 1000 + 2200) which will have disadvantage of weighing down the tables

The alogorithm handles directed and undirected edges. So you would need to enter the data as follows. This can be done with a union query

L'alogorithme gère les bords orientés et non orientés. Vous devez donc saisir les données comme suit. Cela peut être fait avec une requête d'union

troncons  troncons_tenant     repere troncon    longueur
68        69                  CLP0UA_+0S18002   2200
69        68                  CLP0UA_+0S18002   2200

SELECT troncons_assoc.troncons AS StartVertex, troncons_assoc.troncons_tenant AS EndVertex, troncons.[repere troncon], troncons.longueur
FROM troncons INNER JOIN troncons_assoc ON troncons.idtroncons = troncons_assoc.troncons
UNION
SELECT troncons_assoc.troncons_tenant AS StartVertex, troncons_assoc.troncons AS EndVertex, troncons.[repere troncon], troncons.longueur
FROM troncons INNER JOIN troncons_assoc ON troncons.idtroncons = troncons_assoc.troncons
ORDER BY 1, 2

 

[Serge.potoczny]

Merci beaucoup, je suis effectivement passé par une requête union, je vais continuer avec cette approche pour voir si j'arrive à la solution que je recherche

 

[MajP]

Try This
Essaye ça

 

[arnelgp]

majp your code is fast, but.
84: BPF60219_CLN is missing in the path.

 

[MajP]

but.
84: BPF60219_CLN is missing in the path.

That is a good point. The OP has this set up different then what is normal. Normally you have Vertices (or Nodes) and Edges (or connections). So I would have Vertices A, B, C and the edges are the distance between

V1 V2 Edge
A B 10
A C 15
B C 2

So the path from A to C is:
Which is A----B----C

The OP set it up as Sections so a section has a start and a distance. So A, B, C would each have a section distance. So his connections of sections A,B,C would look like
A----B----C----

The problem was in the pulldowns. I used a query for the edges. So the edge sections in the pulldowns were not correct.

 

[Serge.potoczny]

please test!

Bonjour, je me suis servi de la proposition de [U]arnelgp[/U] qui a l'avantage de permettre les parcours dans les 2 sens sans ajouter de requête d'union,
Pourriez vous m'indiquer comment récupérer la longueur totale ?

 

[arnelgp]

added the Distance calculation.

 

[MajP]

Although using a union seems pretty simple in my opinion. If you want my code to do the work for you, add a line of code for the reverse route.
Here is the whole code with the line added.

Bien que l'utilisation d'un syndicat me semble assez simple. Si vous voulez que mon code fasse le travail pour vous, ajoutez une ligne de code pour l'itinéraire inverse.
Voici le code entier avec la ligne ajoutée

Private Sub CmdCalculate_Click()
  Dim Path As String
  Dim rs As DAO.Recordset
  If Not Trim(Me.cmboEnd & "") = "" And Not Trim(Me.cmboStart & " ") = "" Then
    Set Verts = New Vertices
    Set edgs = New Edges
    Set rs = CurrentDb.OpenRecordset("qryNodesTrocon")
 
    Do While Not rs.EOF
     Verts.Add rs!StartVertex, rs!Route
     rs.MoveNext
   Loop

  Set rs = CurrentDb.OpenRecordset("qryEdgesTrocon")
  Do While Not rs.EOF
    edgs.AddEdge rs!StartVertex, rs!EndVertex, rs![EdgeWeight]
   '******ADD this line of code to add reverse route ********
    edgs.AddEdge rs!EndVertex, rs!StartVertex, rs![EdgeWeight]
    '*********************************************************
    rs.MoveNext
  Loop
   Set dij = New Dijkstra
   dij.InitializeDijkstra Verts, edgs
   dij.RunShortestPath Me.cmboStart, Me.cmboEnd
   Me.txtOut = ""
   Me.txtOut = Me.txtOut & "Path IDs: " & vbCrLf & dij.ShortestPath_IDs & vbCrLf & vbCrLf
   Me.txtOut = Me.txtOut & "Path Names: " & vbCrLf & dij.ShortestPath_Names & vbCrLf & vbCrLf
   Me.txtOut = Me.txtOut & "Distance: " & vbCrLf & dij.ShortestPathDistance & vbCrLf & vbCrLf
End If
End Sub

 

[Serge.potoczny]

merci beaucoup, je vais pouvoir avancer dans mon projet, j'aurais probablement encore besoin d'aide un peu plus tard

 

[Robrobby]

What a let down. I figured you needed this algorithm to solve the shortest path for defeating Corona virus transmission, but based on the names it looks like you are trying to find the fastest way to win in the online game Everquest. So much for helping to save the world . I did the floyd-warshall solution if you need it, but I will have to set up a google drive if you want it. If you just need to check one at a time, you should be good. Thanks, this was good practice and interesting.

Just an update, I've been working with this contantly since the day you created it.

A big thankyou again for your hard work and expertise.