如何修改Dijkstra算法来找出所有可能的路径？ [英] How to modify dijkstra algorithm to find all possible paths?

问题描述

我知道，可能之前已经问，但我不能找到它。 我需要修改下面的Dijkstra算法，它的工作原理对于查找 2节点之间的最短路径，但我需要找到所有可能的路径也。 我知道这应该是比较容易做到这一点，但到目前为止，我没有想法 如何做到这一点最简单的方法。我使用的是向加权图。

 类的Dijkstra
    {
        私人列表＆LT;节点＆GT; _nodes;
        私人列表＆LT;边缘＆GT; _edges;
        私人列表＆LT;节点＆GT; _基础;
        私人字典＆LT;字符串，双＆GT; _dist;
        私人字典＆LT;字符串，节点GT; _ previous;

        公共Dijkstra算法（名单＆LT;边缘＆GT;的边缘，名单，其中，节点个节点）
        {

            边=边缘;
            节点=节点，
            基准=新的名单，其中，节点＆GT;（）;
            DIST =新字典＆LT;字符串，双＆GT;（）;
            previous =新字典＆LT;字符串，节点和GT;（）;

            //记录节点
            的foreach（节点n节点）
            {
                previous.Add（n.Name，NULL）;
                Basis.Add（N）;
                Dist.Add（n.Name，double.MaxValue）;
            }
        }

        ///计算​​从开始的最短路径
        ///所有其​​他节点
        公共无效calculateDistance（节点开始）
        {
            DIST [start.Name] = 0;

            而（Basis.Count大于0）
            {
                节点u = getNodeWithSmallestDistance（）;
                如果（U == NULL）
                {
                    Basis.Clear（）;
                }
                其他
                {
                    的foreach（节点V IN getNeighbors（U））
                    {
                        双ALT = DIST [u.Name] + getDistanceBetween（U，V）;
                        如果（ALT＆LT;测距[v.Name]）
                        {
                            DIST [v.Name] = ALT;
                            previous [v.Name] = U;
                        }
                    }
                    Basis.Remove（U）;
                }
            }
        }

        公开名单＆LT;节点＆GT; getPathTo（节点D）
        {
            名单＆LT;节点＆GT;路径=新的名单，其中，节点＆GT;（）;

            path.Insert（0，D）;

            而（previous [d.Name]！= NULL）
            {
                D = previous [d.Name]
                path.Insert（0，D）;
            }

            返回路径;
        }

    公共节点getNodeWithSmallestDistance（）
        {
            双距离= double.MaxValue;
            节点最小= NULL;

            的foreach（节点n依据）
            {
                如果（DIST [n.Name]＆LT;距离）
                {
                    距离= DIST [n.Name]
                    最小= N;
                }
            }

            返回最小的;
        }


        公开名单＆LT;节点＆GT; getNeighbors（节点N）
        {
            名单＆LT;节点＆GT;邻居=新的名单，其中，节点＆GT;（）;

            的foreach（在边缘边e）
            {
                如果（e.Origin.Equals（正）及＆安培; Basis.Contains（n））的
                {
                    neighbors.Add（e.Destination）;
                }
            }

            返回的邻居;
        }

       公共双getDistanceBetween（节点0，节点D）
        {
            的foreach（在边缘边e）
            {
                如果（e.Origin.Equals（O）及和放大器; e.Destination.Equals（D））
                {
                    返回e.Distance;
                }
            }

            返回0;
        }


        公开名单＆LT;节点＆GT;节点
        {
            {返回_nodes; }
            集合{_nodes =价值; }
        }

        公开名单＆LT;边缘＆GT;边缘
        {
            {返回_edges; }
            集合{_edges =价值; }
        }

        公开名单＆LT;节点＆GT;基础
        {
            {返回_basis; }
            集合{_basis =价值; }
        }

        公共字典＆LT;字符串，双＆GT; DIST
        {
            {返回_dist; }
            集合{_dist =价值; }
        }

        公共字典＆LT;字符串，节点GT; previous
        {
            得到{_ previous; }
            集合{_ previous =价值; }
        }
    }
}

静态无效的主要（字串[] args）
        {
//节点初始化到这里

Dijkstra算法D =新Dijkstra算法（_edges，_nodes）;
d.calculateDistance（_dictNodes [A]）;
 名单＆LT;节点＆GT; PATH = d.getPathTo（_dictNodes [C]）;
}
 

解决方案

OK，其实我已经改进Dijkstra课上做BFS，以及它给了我所有可能的途径。我加入这个方法：

 公共无效BreadthFirst（边图，链表＆LT;字符串＆GT;参观）
{
    链表＆LT;字符串＆GT;节点= graph.adjacentNodes（visited.Last（））;

    //检查相邻节点
    的foreach（在节点字符串节点）
    {
        如果（visited.Contains（节点））
        {
            继续;
        }

        如果（node.Equals（终端节点））
        {
            visited.AddLast（节点）;

            printPath（参观）;

            visited.RemoveLast（）;

            打破;
         }
     }

    //在广度优先，递归需求者前来参观相邻节点后，
    的foreach（在节点字符串节点）
    {
        如果（visited.Contains（节点）|| node.Equals（终端节点））
        {
            继续;
        }

        visited.AddLast（节点）;

        //递归
        BreadthFirst（图参观）;

        visited.RemoveLast（）;
    }
}
 

使用情况会是这样的：

  Dijkstra算法D =新Dijkstra算法（_edges，_nodes）;

链表＆LT;字符串＆GT;走访=新的LinkedList＆LT;字符串＆GT;（）; //收集所有路线
visited.AddFirst（开始）;

d.BreadthFirst（图参观）;
 

I know that could be asked before already but I cannot find it. I need to modify below dijkstra algorithm which works good for finding shortest path between 2 nodes but I need to find all possible paths also. I know it should be relatively easy to do this but so far I don't have idea how to do this simplest way. I'm using directed weighted graph.

    class Dijkstra
    {
        private List<Node> _nodes;
        private List<Edge> _edges;
        private List<Node> _basis;
        private Dictionary<string, double> _dist;
        private Dictionary<string, Node> _previous;

        public Dijkstra(List<Edge> edges, List<Node> nodes)
        {

            Edges = edges;
            Nodes = nodes;
            Basis = new List<Node>();
            Dist = new Dictionary<string, double>();
            Previous = new Dictionary<string, Node>();

            // record node 
            foreach (Node n in Nodes)
            {
                Previous.Add(n.Name, null);
                Basis.Add(n);
                Dist.Add(n.Name, double.MaxValue);
            }
        }

        /// Calculates the shortest path from the start
        ///  to all other nodes
        public void calculateDistance(Node start)
        {
            Dist[start.Name] = 0;

            while (Basis.Count > 0)
            {
                Node u = getNodeWithSmallestDistance();
                if (u == null)
                {
                    Basis.Clear();
                }
                else
                {
                    foreach (Node v in getNeighbors(u))
                    {
                        double alt = Dist[u.Name] + getDistanceBetween(u, v);
                        if (alt < Dist[v.Name])
                        {
                            Dist[v.Name] = alt;
                            Previous[v.Name] = u;
                        }
                    }
                    Basis.Remove(u);
                }
            }
        }

        public List<Node> getPathTo(Node d)
        {
            List<Node> path = new List<Node>();

            path.Insert(0, d);

            while (Previous[d.Name] != null)
            {
                d = Previous[d.Name];
                path.Insert(0, d);
            }

            return path;
        }

    public Node getNodeWithSmallestDistance()
        {
            double distance = double.MaxValue;
            Node smallest = null;

            foreach (Node n in Basis)
            {
                if (Dist[n.Name] < distance)       
                {
                    distance = Dist[n.Name];
                    smallest = n;
                }
            }

            return smallest;
        }


        public List<Node> getNeighbors(Node n)
        {
            List<Node> neighbors = new List<Node>();

            foreach (Edge e in Edges)
            {
                if (e.Origin.Equals(n) && Basis.Contains(n))
                {
                    neighbors.Add(e.Destination);
                }
            }

            return neighbors;
        }

       public double getDistanceBetween(Node o, Node d)
        {
            foreach (Edge e in Edges)
            {
                if (e.Origin.Equals(o) && e.Destination.Equals(d))
                {
                    return e.Distance;
                }
            }

            return 0;
        }


        public List<Node> Nodes
        {
            get { return _nodes; }
            set { _nodes = value; }
        }

        public List<Edge> Edges
        {
            get { return _edges; }
            set { _edges = value; }
        }

        public List<Node> Basis
        {
            get { return _basis; }
            set { _basis = value; }
        }

        public Dictionary<string, double> Dist
        {
            get { return _dist; }
            set { _dist = value; }
        }

        public Dictionary<string, Node> Previous
        {
            get { return _previous; }
            set { _previous = value; }
        }
    }
}

static void Main(string[] args)
        {
//Nodes initialisation goes here

Dijkstra d = new Dijkstra(_edges, _nodes);
d.calculateDistance(_dictNodes["A"]);
 List<Node> path = d.getPathTo(_dictNodes["C"]);
}

解决方案

OK, I have actually modified Dijkstra class to do BFS as well and it got me all possible routes. I added this method:

public void BreadthFirst(Edge graph, LinkedList<String> visited) 
{
    LinkedList<String> nodes = graph.adjacentNodes(visited.Last());

    // Examine adjacent nodes
    foreach (String node in nodes) 
    {
        if (visited.Contains(node))
        {
            continue;
        }

        if (node.Equals(endNode))
        {
            visited.AddLast(node);

            printPath(visited);

            visited.RemoveLast();

            break;
         }
     }

    // In breadth-first, recursion needs to come after visiting adjacent nodes
    foreach (String node in nodes)
    {      
        if(visited.Contains(node) || node.Equals(endNode))
        {
            continue;
        }

        visited.AddLast(node);

        // Recursion
        BreadthFirst(graph, visited);

        visited.RemoveLast();
    }
}

Usage would be like this:

Dijkstra d = new Dijkstra(_edges, _nodes);

LinkedList<String> visited = new LinkedList<string>();  //collecting all routes
visited.AddFirst(start);

d.BreadthFirst(graph, visited);

这篇关于如何修改Dijkstra算法来找出所有可能的路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！