Wrong implementation of Dijkstra's trying to return weight

[Vyom-Yadav]

https://github.com/SkienaBook/Algorithm-Design-Manual-Programs-V3/blob/9bdfcc0203956c354cfc9715559a8671a73684cb/dijkstra.c#L36-L81

The algorithm returns weight. Now nowhere in the book is clarified what is this weight. The weight that this algorithm returns relates to no sort of weight. It is not the weight of the MST. It is not the weight of all the edges that the Dijkstra graph uses, i.e. shortest path edges.

The book states that:

Below, we give an implementation of Dijkstra's algorithm based on changing exactly four lines from our Prim's implementation..........

This gives the reader a false sense that the algorithm is capable of both:

• Finding the shortest path from a single source
• Weight of the MST of the given graph

https://github.com/SkienaBook/Algorithm-Design-Manual-Programs-V3/blob/9bdfcc0203956c354cfc9715559a8671a73684cb/dijkstra.c#L57-L60

This weight addition is pointless. If the intention is to find the weight of the MST, then this is wrong. It is not possible to find the weight of MST in Dijkstra's algorithm (unless you add extra conditions) due to what the distance[] array represents.

https://stackoverflow.com/a/65319310/15412365 gives a good example illustrating why we can't find a relation between Dijsktra's graph and MST.

---

I feel these points should have been covered in the book.

Cc @SkienaBook, sir, please take a look.

Thanks and Regards, Vyom

[Vyom-Yadav]

Also, the book contains O(n^2) Dijkstra, I strongly feel, like it was mentioned for Prim's that a better implementation exists, the same should have been mentioned for Dijkstra.

I wrote an O(n*log n) implementation in Java:

public static DijkstraOutput efficientDijkstraForShortestPath(Graph g, int start) {           
    int nVertices = g.getNvertices();                                                         
    int[] parent = new int[nVertices];                                                        
    Edge[] edges = g.getEdges();                                                              
    int[] distance = new int[nVertices];                                                      

    for (int i = 0; i < nVertices; i++) {                                                     
        distance[i] = Integer.MAX_VALUE;                                                      
        parent[i] = -1;                                                                       
    }                                                                                         

    distance[start] = 0;
    Queue<AbstractMap.SimpleEntry<Integer, Integer>> nodes =                                  
            new PriorityQueue<>(Comparator.comparingInt(AbstractMap.SimpleEntry::getValue));  

    nodes.add(new AbstractMap.SimpleEntry<>(start, 0));                                       

    int count = 0;                                                                            
    boolean[] inTree = new boolean[nVertices];                                                
    while (!nodes.isEmpty()) {                                                                
        if (count == nVertices) {                                                             
            break;                                                                            
        }                                                                                     
        AbstractMap.SimpleEntry<Integer, Integer> nodeWithWeight = nodes.poll();              
        int node = nodeWithWeight.getKey();                                                   
        if (!inTree[node]) {                                                                  
            count++;                                                                          
            inTree[node] = true;                                                              
            Edge e = edges[node];                                                             
            while (e != null) {                                                               
                int y = e.y;                                                                  
                if (distance[y] > distance[node] + e.weight) {                                
                    distance[y] = distance[node] + e.weight;                                  
                    parent[y] = node;                                                         
                    nodes.add(new AbstractMap.SimpleEntry<>(y, distance[y]));                 
                }                                                                             
                e = e.next;                                                                   
            }                                                                                 
        }                                                                                     
    }                                                                                         
    return new DijkstraOutput(parent, distance);                                              
}                                                                                             

[SkienaBook]

Thanks -- I will sent this aside to consider when I do the next edition of my book.

Steven Skiena

On Mon, Sep 25, 2023 at 6:05 AM Vyom Yadav @.***> wrote:

https://github.com/SkienaBook/Algorithm-Design-Manual-Programs-V3/blob/9bdfcc0203956c354cfc9715559a8671a73684cb/dijkstra.c#L36-L81

The algorithm returns weight. Now nowhere in the book is clarified what is this weight. The weight that this algorithm returns relates to no sort of weight. It is not the weight of the MST. It is not the weight of all the edges that the Dijkstra graph uses, i.e. shortest path edges.

The book states that:

Below, we give an implementation of Dijkstra's algorithm based on changing exactly four lines from our Prim's implementation..........

This gives the reader a false sense that the algorithm is capable of both:

Finding the shortest path from a single source Weight of the MST of the given graph

https://github.com/SkienaBook/Algorithm-Design-Manual-Programs-V3/blob/9bdfcc0203956c354cfc9715559a8671a73684cb/dijkstra.c#L57-L60

This weight addition is pointless. If the intention is to find the weight of the MST, then this is wrong. It is not possible to find the weight of MST in Dijkstra's algorithm (unless you add extra conditions) due to what the distance[] array represents.

https://stackoverflow.com/a/65319310/15412365 gives a good example illustrating why we can't find a relation between Dijsktra's graph and MST.

---

I feel these points should have been covered in the book.

Cc @SkienaBook, sir, please take a look.

Thanks and Regards, Vyom

— Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you were mentioned.Message ID: @.***>