JavaScript-图形遍历 - 返回最短路径

Question

我想穿越图形。我有两个结构：

var Node = function(name) {  
    this.edge_list = [];
    this.name = name;
};

和

var Graph = function() {  
    this.node_list = [];
};

将边缘添加到这样的节点：

Node.prototype.addEdge = function(end, distance) {  
    this.edge_list.push({end, distance});
};

图看起来像这样：

start:
[ Object { end: '1', distance: 13 },
  Object { end: '2', distance: 14 } ]
1:
[ Object { end: 'start', distance: 13 },
  Object { end: '3', distance: 2 } ]
2:
[ Object { end: 'start', distance: 14 },
  Object { end: '3', distance: 1 } ]
3:
[ Object { end: '1', distance: 2 },
  Object { end: '2', distance: 1 },
  Object { end: 'end', distance: 10 } ]
end:
[ Object { end: '3', distance: 10 } ]

我要做的是创建一个功能，该功能将返回最短的距离/路径从source返回到target。

我目前有测试https://repl.it/c6fh

Answer 1

如果距离为正，则dijkstra就是要走的路。但是，一种非常简单的算法是：

• 标记每个节点具有无限距离，源节点的距离为0。
• 从源头开始在图表上执行宽度优先的遍历：
  • 如果当前边缘导致较小的距离，则更新节点的距离
  • 将节点添加到队列的末端

以下是我的快速解决方案，该解决方案将距离和以前的节点存储在您的节点类中。

您会在节点本身上找到最小距离，例如dstNode.distance。对于路径，只需从dstNode追踪并按照prev链接。

function shortest_path(g, src, dst) {
    var get_node = function(n) {
        for (var i = 0; i < g.node_list.length; i++) {
            if (g.node_list[i].name == n) {
                return g.node_list[i];
            }
        }
        return null;
    }
    var srcNode = get_node(src);
    var dstNode = get_node(dst);
    for(var i = 0; i < g.node_list.length; i++) {
        // think of as infinity (currently assumed to be unreachable)
        g.node_list[i].distance = 2147483647;
        g.node_list[i].prev = null;
    }
    srcNode.distance = 0; // src node is of distance zero from itself
    q = [srcNode]; // we will breadth-first traverse the graph
    while (q.length > 0) {
        var cur = q[0];
        q.shift();
        for (var i = 0; i < cur.edge_list.length; i++) {
            n = get_node(cur.edge_list[i].end);
            // here we are looping through neighbors of cur
            // to see if a smaller distance exists
            if (n.distance > cur.distance + cur.edge_list[i].distance) {
                n.distance = cur.distance + cur.edge_list[i].distance;
                n.prev = cur;
                q.push(n);
            }
        }
    }
}