javascript - JavaScript中多向网络的路由或寻路算法

Question

我正在尝试用 JavaScript 为以下由节点组成的网络编写路由/路径查找算法。每个节点都有规则来管理它是否可以作为入口点、导出点和/或被遍历。

如果选择了一个有效的入口点，我需要解决以下两个问题:

1. 网络的有效和可用导出点是什么
2. 一旦确定并选择了有效的导出点，最佳路线是什么(需要遍历的节点)

网络规则:

1. 您只能进入具有入口点的节点，即节点 A、B、C、D、E、F、G
2. 您只能退出具有退出点的节点，即节点 B、C、E、、F、G
3. 行进方向由入口节点决定 - 这决定了您可以行进和退出的方向。 。例如。经节点A进入时顺时针行进退出
4. 一旦进入网络就不能改变方向。

我将网络表示为一个对象数组，数组中的每个对象代表网络上的一个节点。

    var network = [{
                     id: 'A',
                     canBeEntry: true,
                     ifEntryRouteIs: 'CW',
                     isExitIfRouteIs: 'N/A',
                     neighbourCW: ['B'],
                     neighbourCCW: ['H']
                    }, {
                     id: 'B',
                     canBeEntry: true,
                     ifEntryRouteIs: 'CW&CCW',
                     isExitIfRouteIs: 'CW',
                     neighbourCW: ['C'],
                     neighbourCCW: ['A']
                    },
                    .
                    .
                    .
                    {
                     id: 'H',
                     canBeEntry: false,
                     ifEntryRouteIs: 'N/A',
                     isExitIfRouteIs: 'N/A',
                     neighbourCW: ['A'],
                     neighbourCCW: ['G']
                    }];

描述有效进入/退出节点、转换和权重的图表如下:

我对与寻路和路由相关的算法(例如 Dijkstra 或 A* 搜索)做了一些或研究，但它们似乎基于成本和权重，我认为这不适用于我的网络。

有没有人对如何用 JavaScript 编写算法来首先确定导出点，然后再确定路线有任何想法或方法？

我试图用 JavaScript 实现的 jsfiddle 在这里 http://jsfiddle.net/mkov/dgGHm/

Answer 1

如果我没理解错的话，你想找到给定的起始节点和方向、可能的导出和到它们的最短路径。这应该有效:(必须稍微修改原始数据):

var validExitPoints =[];
    var nodes=[];
    var tree_path=[];
    nodes.push({node:entryPoint});
    visited[entryPoint]=true;
    while(!nodes.length==0){
        var node=network_obj[nodes[0].node];

        nodes.shift();
        if(canExit(node.id,dir)){
            validExitPoints.push({node:node.id,path:''});
        }
        var neighbours=getNeighbours(node.id,dir);
        for(var i=0;i<neighbours.length;i++){
            if(visited[neighbours[i]]==false){
                nodes.push({node:neighbours[i]});
                visited[neighbours[i]]=true;
                tree_path[neighbours[i]]=node.id;
            }
        }
    }

这就是主要代码，完整代码在这里:

http://jsfiddle.net/juvian/dgGHm/6/

我为此使用了广度优先搜索，您可以在这里阅读更多相关信息:

http://en.wikipedia.org/wiki/Breadth-first_search