时间戳

首页 > 解决方案 > 在有边界的 2 个国家之间找到路径

javascript - 在有边界的 2 个国家之间找到路径

问题描述

我有来自某个大陆的国家/地区的 JSON。每个国家都有一个数组，其中包含其边界国家。给定来自同一大陆的 2 个国家，返回它的路线。例如：巴西和美国 -> 1. 哥伦比亚，2. 巴拿马，3. 哥斯达黎加，4. 尼加拉瓜，5. 洪都拉斯，6. 危地马拉，7. 墨西哥。

我正在努力将它组织在一个阵列上，只是为了进行 BFS（广度优先搜索）。到目前为止我所拥有的是：

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'])

这是 JSON 示例：https ://restcountries.eu/rest/v2/region/americas

我认为我的主要问题是我正在努力将这个 JSON 转换为 GRAPH。

标签： javascriptalgorithmbreadth-first-search

解决方案

检查Dijkstra 的算法，您可以在其中假设国家作为算法中的节点，与邻国的距离为 1，而非邻国没有边界。

编辑：这是使用您指定的数据的实现。将从 JSON 样本（整个数组）中获取的数据作为图形参数、源国家（例如“BRA”）、目标国家（例如“USA”）传递。我没有做很多测试，所以我不能保证这是没有错误的。

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;
}

推荐阅读