Ruta más corta en JavaScript

Nuestros mejores programadores han agotado sus reservas de café, por su búsqueda todo el tiempo por la solución, hasta que Juliana encontró la solución en Gogs por lo tanto hoy la comparte aquí.

Solución:

Comencemos por señalar que la búsqueda en amplitud (BFS) calcula las rutas más cortas desde un vértice de origen dado si el gráfico no está ponderado. En otras palabras, consideramos que la longitud de una ruta es el número de bordes en la ruta.

A continuación, se muestra una forma sencilla de construir un gráfico no ponderado:

function Graph() 
  var neighbors = this.neighbors = ; // Key = vertex, value = array of neighbors.

  this.addEdge = function (u, v) 
    if (neighbors[u] === undefined)   // Add the edge u -> v.
      neighbors[u] = [];
    
    neighbors[u].push(v);
    if (neighbors[v] === undefined)   // Also add the edge v -> u so as
      neighbors[v] = [];               // to implement an undirected graph.
                                      // For a directed graph, delete
    neighbors[v].push(u);              // these four lines.
  ;

  return this;

Tenga en cuenta que hemos implementado un gráfico no dirigido. Como se menciona en los comentarios en línea, puede modificar el código para construir un gráfico dirigido eliminando cuatro líneas del addEdge función.

Esta implementación de BFS funcionaría igualmente bien en un gráfico dirigido:

function bfs(graph, source) 
  var queue = [  vertex: source, count: 0  ],
      visited =  source: true ,
      tail = 0;
  while (tail < queue.length) 
    var u = queue[tail].vertex,
        count = queue[tail++].count;  // Pop a vertex off the queue.
    print('distance from ' + source + ' to ' + u + ': ' + count);
    graph.neighbors[u].forEach(function (v) 
      if (!visited[v]) 
        visited[v] = true;
        queue.push( vertex: v, count: count + 1 );
      
    );
  

Para encontrar la ruta más corta entre dos vértices dados y mostrar los vértices a lo largo de la ruta, tenemos que recordar el predecesor de cada vértice mientras exploramos el gráfico:

function shortestPath(graph, source, target) 
  if (source == target)    // Delete these four lines if
    print(source);          // you want to look for a cycle
    return;                 // when the source is equal to
                           // the target.
  var queue = [ source ],
      visited =  source: true ,
      predecessor = ,
      tail = 0;
  while (tail < queue.length) 
    var u = queue[tail++],  // Pop a vertex off the queue.
        neighbors = graph.neighbors[u];
    for (var i = 0; i < neighbors.length; ++i) 
      var v = neighbors[i];
      if (visited[v]) 
        continue;
      
      visited[v] = true;
      if (v === target)    // Check if the path is complete.
        var path = [ v ];   // If so, backtrack through the path.
        while (u !== source) 
          path.push(u);
          u = predecessor[u];          
        
        path.push(u);
        path.reverse();
        print(path.join(' → '));
        return;
      
      predecessor[v] = u;
      queue.push(v);
    
  
  print('there is no path from ' + source + ' to ' + target);

El siguiente fragmento demuestra estas operaciones en el gráfico que proporcionó en su pregunta. Primero encontramos los caminos más cortos a todos los vértices accesibles desde A. Entonces encontramos el camino más corto desde B para G y de G para A.

function Graph() 
  var neighbors = this.neighbors = ; // Key = vertex, value = array of neighbors.

  this.addEdge = function (u, v) 
    if (neighbors[u] === undefined)   // Add the edge u -> v.
      neighbors[u] = [];
    
    neighbors[u].push(v);
    if (neighbors[v] === undefined)   // Also add the edge v -> u in order
      neighbors[v] = [];               // to implement an undirected graph.
                                      // For a directed graph, delete
    neighbors[v].push(u);              // these four lines.
  ;

  return this;


function bfs(graph, source) 
  var queue = [  vertex: source, count: 0  ],
      visited =  source: true ,
      tail = 0;
  while (tail < queue.length) 
    var u = queue[tail].vertex,
        count = queue[tail++].count;  // Pop a vertex off the queue.
    print('distance from ' + source + ' to ' + u + ': ' + count);
    graph.neighbors[u].forEach(function (v) 
      if (!visited[v]) 
        visited[v] = true;
        queue.push( vertex: v, count: count + 1 );
      
    );
  


function shortestPath(graph, source, target) 
  if (source == target)    // Delete these four lines if
    print(source);          // you want to look for a cycle
    return;                 // when the source is equal to
                           // the target.
  var queue = [ source ],
      visited =  source: true ,
      predecessor = ,
      tail = 0;
  while (tail < queue.length) 
    var u = queue[tail++],  // Pop a vertex off the queue.
        neighbors = graph.neighbors[u];
    for (var i = 0; i < neighbors.length; ++i) 
      var v = neighbors[i];
      if (visited[v]) 
        continue;
      
      visited[v] = true;
      if (v === target)    // Check if the path is complete.
        var path = [ v ];   // If so, backtrack through the path.
        while (u !== source) 
          path.push(u);
          u = predecessor[u];
        
        path.push(u);
        path.reverse();
        print(path.join(' → '));
        return;
      
      predecessor[v] = u;
      queue.push(v);
    
  
  print('there is no path from ' + source + ' to ' + target);


function print(s)  '';
  document.getElementById('display').innerHTML += s + '
';


window.onload = function () 
  var graph = new Graph();
  graph.addEdge('A', 'B');
  graph.addEdge('B', 'C');
  graph.addEdge('B', 'E');
  graph.addEdge('C', 'D');
  graph.addEdge('C', 'E');
  graph.addEdge('C', 'G');
  graph.addEdge('D', 'E');
  graph.addEdge('E', 'F');

  bfs(graph, 'A');
  print();
  shortestPath(graph, 'B', 'G');
  print();
  shortestPath(graph, 'G', 'A');
;

body  
  font-family: 'Source Code Pro', monospace;
  font-size: 12px;

Al leer su pregunta, puedo leerla de dos maneras ... O está tratando de reducir la cantidad de cosas que verifica, o está tratando de permitirse pasar variables para cambiar los puntos finales. Asumiré lo primero y dejaré que otra persona se encargue del segundo caso.

Al echar un vistazo rápido al problema, parece que se ha encontrado con lo que se conoce en Comp Sci como "El problema del viajante de comercio". Es un problema clásico en la programación de computadoras que se considera una imposibilidad lógica y es un buen ejemplo de que "lo perfecto es enemigo de lo bueno".

El problema clásico del viajante de comercio es este: "Programe una forma para que un vendedor llegue a todas sus ciudades de destino en un mapa en el menor tiempo posible. Hágalo sin tener que comprobar todos los caminos posibles". La cuestión es que (todavía) no se ha descubierto (todavía) una forma lógica de hacer esto (todavía no se ha demostrado si es imposible o posible). Dicho esto, si no tiene que ser EL más corto, sino solo un camino más corto, hay varios atajos que se pueden tomar. Un ejemplo es simplemente calcular una línea de principio a fin y luego presionar las desviaciones para que coincidan con los vértices más cercanos. Otra es dividir las rutas en triángulos que conectan cada vértice solo con los dos vértices más cercanos y luego conectar los grupos de la misma manera hasta que todos los vértices estén conectados y luego solo calcular las rutas potenciales iniciales de esos subconjuntos.

Ninguna de esas dos respuestas está garantizada para darle la mejor respuesta, pero le proporcionarán una buena respuesta con mucho menos tiempo computacional requerido para que no tenga que calcular todas las rutas provenientes de A y B y C, etc., etc.

Sección de Reseñas y Valoraciones

Acuérdate de que tienes concesión de agregar una reseña si te ayudó.

---

---

Utiliza Nuestro Buscador