Le plus court chemin avec un réservoir de carburant

Question

Ceci est une question de devoirs et je serais heureux pour quelques conseils. Soit G = (V, E) un graphe non orienté où chaque sommet représente une ville, et les arêtes ont des poids qui représentent les distances de déplacement. Certaines villes ont des stations-service. Une voiture commence à partir des sommets avec un réservoir de gaz suffisant pour parcourir la longueur L. J'ai besoin de trouver le chemin le plus court entre s et t afin que la voiture ne manquera pas de gaz.

Ma pensée principale était d'utiliser l'algorithme de Floyd-Warshall avec quelques changements. Lorsque nous calculons shortestPath (i, j, 0), nous affectons w (i, j) si i a une station d'essence et L-w (i, j)> 0, et l'infini sinon. Cependant, pour les prochaines étapes, je ne sais pas comment ajouter l'état actuel du carburant dans les calculs.

Merci.

Answer 1

Créer un nouveau graphique pondéré avec les sommets: s, t et les villes (C) avec station d'essence.

Bords:

• s-c, avec c de C, s'il existe un chemin le plus court entre s et c a une longueur <= L,
• c1-c2, avec c1, c2 de C, avec une longueur c1-c2 <= L,
• c-t, avec c à partir de C, avec le ngth c-e <= L,
• s-t, si longueur s-t <= L.

et le poids de bord défini à la longueur v1-v2.

Dijkstra standard sur ce graphique devrait retourner le squelette du plus court chemin que vous recherchez sur le graphique original.

Il est possible de créer un nouveau graphe «itérativement» lorsque Dijkstra demande des arêtes sur les sommets de frontière. Quelque chose comme, créer d'abord s-c et s-t arêtes (et sommets), et s'il y a une demande pour c1-c2 et c-t que d'ajouter ces sommets et arêtes à un graphique.