Find path between 2 countries with borders

Question

I Have a JSON with countries from a continent. Each country has a array that has it's border countries. Given 2 countries from the same continent, return it's route. E.g.: Brazil and USA -> 1. Colômbia, 2. Panamá, 3. Costa Rica, 4. Nicarágua, 5. Honduras, 6. Guatemala, 7. México.

I'm struggling to organize it on one array only to make a BFS (Breadth First Search). What i have until now is:

function traverse(main_key, obj) {

obj.forEach(function(key) {
if (visited[main_key] === undefined) {
    visited[main_key] = new Array()
}

visited[main_key].push(obj)

if (typeof(borders[key]) === 'array' && visited[main_key].indeOf(key) !== -1) {
  traverse(borders[key])
} 
  else {
      //do something with the actual value
      console.log(main_key, borders[key], key)
    }
  })      
};

traverse('BRA', borders['BRA'])

Here is JSON sample: https://restcountries.eu/rest/v2/region/americas

I think my main problem is i'm struggling with transforming this JSON into a GRAPH.

Please elaborate on what you are trying to do and provide a clear example. — Unmitigated
Given 2 countries from the same continent, return it's route. E.g.: Start Brazil, END USA -> 1. Colômbia, 2. Panamá, 3. Costa Rica, 4. Nicarágua, 5. Honduras, 6. Guatemala, 7. México. What's not clear? I know i need to do a recursive function to find the path. — Marco

Sherif Elmetainy Sherif Elmetainy · Accepted Answer · 2020-08-16T20:33:48

Checkout Dijkstra's algorithm where you can assume that countries as nodes in the algorithm and bordering countries have a distance of 1 and non-bordering countries don't have borders.

Edit: Here is an implementation using the data you specified. Pass the data you get from the JSON sample (entire array) as the graph parameter, source country (for example 'BRA'), target country (for example 'USA'). I didn't do a lot of testing, so I can't guarantee this is bug free.

function dijkstra(graph, source, target) {
  var dist = {};
  var prev = {};
  var vertices = [];
  for (var i = 0; i < graph.length; i++) {
    var vertex = graph[i];
    dist[vertex.alpha3Code] = Infinity;
    prev[vertex.alpha3Code] = null;
    vertices.push(vertex);
  }
  dist[source] = 0;

  while (vertices.length > 0) {
    // Find the vertex having smallest dist.
    var u = vertices.reduce(function(p, current) {return !p || dist[current.alpha3Code] < dist[p.alpha3Code] ? current : p;}, null);
    const index = vertices.indexOf(u);
    vertices.splice(index, 1);
    if (u.borders && Array.isArray(u.borders)) {
      for (var i = 0; i < u.borders.length; i++) {
        var v = u.borders[i];
        const alt = dist[u.alpha3Code] + 1;
        if (alt < dist[v]) {
          dist[v] = alt;
          prev[v] = u;
        }
      }
    }
  }
  var result = [];
  while (target) {
    result.splice(0, 0, target);
    target = prev[target] ? prev[target].alpha3Code : null;
  }
  // Any empty array return means there is no path. For example one of the countries is an island.
  if (result.length === 1) {
    return [];
  }
  return result;
}

Find path between 2 countries with borders

1 Answers