-1
$\begingroup$

i tried both algorithm to find the shortest path with minimal cost between two vertices,but most of the time Dijkstra gives a different path and the cost is smaller than the cost for the path UCS gives, is this right or there is something wrong with my code?

edit: here's the code for both algorithms implemented in java p.s the graph has two- way edges

public void UCS(Vertex source, Vertex goal) {
        
        source.setDistance(0);
        PriorityQueue<Vertex> queue = new PriorityQueue<Vertex>(20,
            new Comparator<Vertex>(){

                //override compare method
                public int compare(Vertex i, Vertex j){
                    if(i.getDistance() > j.getDistance()){
                        return 1;
                    }

                    else if (i.getDistance() < j.getDistance()){
                        return -1;
                    }

                    else{
                        return 0;
                    }
                }
            }

        );

        queue.add(source);

        Set<Vertex> explored = new HashSet<Vertex>();
        boolean found = false;

        //while frontier is not empty
        do{

            Vertex current = queue.poll();
            explored.add(current);


            if(current.getName().matches(goal.getName())){
                found = true;

            }




            for(Vertex child: current.getAdjacentCities()){

                Edge e = findEdge(child, current);

                double cost = e.getCost();
                child.setDistance(current.getDistance() + cost);

                if(!explored.contains(child) && !queue.contains(child)){

                    child.setDistance(cost+current.getDistance());
                    child.setPath(current);
                    queue.add(child);

                }
                else if((queue.contains(child))&&(child.getDistance()>(current.getDistance()+cost))){
                    child.setPath(current);

                    child.setDistance(current.getDistance()+cost);
                    // the next two calls decrease the key of the node in the queue
                    queue.remove(child);
                    queue.add(child);
                }


            }
        }while(!queue.isEmpty()&&(found==false));


Dijkstra:

public void dijkstra(Vertex fromCity)
    {
        for (Vertex v : vertices)
        {
            v.setDistance(Integer.MAX_VALUE);
            v.setPath(null);
        }

        Vertex fromLocal = findVertex(fromCity);
        fromLocal.setDistance(0);

        PriorityQueue<Vertex> heap = new PriorityQueue<>();
        heap.add(fromLocal);

        while (!heap.isEmpty() )
        {
            Vertex u = heap.poll();

            for (Vertex adjacent : u.getAdjacentCities())
            {
                Edge e = findEdge(u, adjacent);
                double newDistance = u.getDistance() + e.getCost();

                if (newDistance < adjacent.getDistance())
                {
                    heap.remove(adjacent);
                    adjacent.setDistance(newDistance);
                    adjacent.setPath(u);
                    heap.add(adjacent);
                }
            }
        }
    }
}
```
$\endgroup$
1
$\begingroup$

This is not the right place to ask for people to review your code, but it's perfectly normal for Dijkstra's algorithm and Uniform Cost Search (BFS) to return different paths. Indeed, a shortest path on a weighted graph is not necessarily the one that uses less edges.

As an example you can consider the graph $G=(V,E)$ with $V=\{s,u,v\}$, $E=\{(s,u), (u,v), (s,v) \}$ and weights $w(s,u)=w(u,v)=1$, $w(s,v)=3$.

The shortest path from $s$ to $v$ w.r.t. the edge weights is $s \to u \to v$ and has weight $2$. The shortest path w.r.t. the hop-distance (i.e., the number of used edges) is $s\to v$.

$\endgroup$
4
  • $\begingroup$ but both algorithms give the shortest path based on the minimal cost not based on the smallest number of edges $\endgroup$ – pinky_dinky_doo400 Apr 10 at 13:04
  • 1
    $\begingroup$ That's not true (or, if you wish, the two algorithms use different cost functions). Uniform cost search, as the name says, assumes that the costs of all edges are the same, i.e., minimizing the total cost of a shortest path is the same of minimizing the number of its edges. Dijkstra's algorithm returns the shortest path in a graph in which each edge can have an arbitrary non-negative weight. A shortest path w.r.t. one cost function is not necessarily also a shortest path w.r.t. the other. $\endgroup$ – Steven Apr 10 at 13:35
  • $\begingroup$ @steven what u said is only true if the cost for all edges is the same, which is not the case here. A friend helped me figure out what is wrong with my code and i just had to delete ``` child.setDistance(current.getDistance() + cost); ``` before the if statement. $\endgroup$ – pinky_dinky_doo400 Apr 11 at 16:25
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Raphael Apr 20 at 23:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.