如何修改dijkstra算法以查找所有可能的路径？

Question

我知道之前可能已经有人问过，但是我找不到。我需要在下面的dijkstra算法中进行修改，该算法非常适合查找2个节点之间的最短路径，但我还需要找到所有可能的路径。我知道这样做相对容易，但到目前为止我还不知道如何做到这一点最简单的方法。我正在使用有向加权图。

    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"]);
}

Answer 1

[好，我实际上已经修改了Dijkstra类，使其也可以做BFS，它为我提供了所有可能的路线。我添加了此方法：

Answer 2

您无法轻易修改Dijkstra以显示所有可能的路径。您需要修改BFS或DFS搜索。

Answer 3

如果要查找所有simple

Answer 4

以下是我在网上找到的几种算法，用于查找图中的所有可能路径。他们没有修改Dijkstra的算法，但我认为他们还是应该做您想要的。

Answer 5

这是使用BFS