Applying Dijkstra Algorithm: Solving a Problem

[evinda]

Hello! (Wave)

I want to apply the Dijkstra algorithm at an example.

Dijkstra(G,s,v)
1. InitialValues(G,s)
2.S<-∅
3.Q<-V // priority queue,with key the field d[]
4. while Q  ≠ ∅
5.         u<-Extraction_of_Minimum(Q)
6.          S<-S U {u}
7.          for each v ∈ Adj[u]
8.               Relaxation(u,v,w)

InitialValues(G,s)
 for each v ∈ V
      d[v]<-oo
      p[v]<-∅
 d[s]<-0

Relaxation(u,v,w)
 if d[v]>d[u]+w(u,v)
    d[v]<-d[u]+w(u,v)
    p[v]<-u

This is the given graph:

View attachment 3127

Executing the algorithm,I found the following:

$$p[a]=s$$
$$p[c]=s$$
$$p=c$$
$$p[d]=a$$

So,the tree,that we get from the Dijkstra's algorithm would be:

View attachment 3128

So,the weight would be $23$.

But...I found the following tree,with less weight:

View attachment 3129

Have I done something wrong,applying the algorithm? (Thinking)

 

[alyafey22]

According to definition, the minimum spanning tree is applied on a connected undirected graph.

So first convert the directed graph to undirected then apply the alogrithm to find the minimum spanning tree.

I'm not sure if there is a version for a directed graph because if you look at the last graph if you move from \(\displaystyle s\) then you are stuck.

 

[evinda]

According to definition, the minimum spanning tree is applied on a connected undirected graph.

So first convert the directed graph to undirected then apply the alogrithm to find the minimum spanning tree.

I'm not sure if there is a version for a directed graph because if you look at the last graph if you move from \(\displaystyle s\) then you are stuck.

I am sorry..I don't want to find the minimum spanning tree.. (Blush)

I wanted to apply the Dijkstra's algorithm at the above example..

So,I have to find a path,that contains all the vertices , such that the sum of the weights of its constituent edges is minimized..right?

So..have I done something wrong? (Thinking)

 

[magneto1]

Dijkstra's algorithm is used to determine the lowest cost path from a given node (the source) $s$ to every other node in the graph. (The graph may be directed or undirected, since an undirected path can be viewed as two opposing directed path with the same weight.)

In the last graph provided, your directed path tree from $s$ can only reach $c$. The cost going from $s$ to $a$ in that path tree in fact is $\infty$ as it is not reachable, but that's not the case.

 

[evinda]

Dijkstra's algorithm is used to determine the lowest cost path from a given node (the source) $s$ to every other node in the graph. (The graph may be directed or undirected, since an undirected path can be viewed as two opposing directed path with the same weight.)

In the last graph provided, your directed path tree from $s$ can only reach $c$. The cost going from $s$ to $a$ in that path tree in fact is $\infty$ as it is not reachable, but that's not the case.

A ok..so is the first graph right? (Thinking)

 

[I like Serena]

A ok..so is the first graph right? (Thinking)

Yes. It gives the shortest path of $\enclose{circle}{s}$ to each of the other nodes. (Wasntme)

 

[evinda]

Yes. It gives the shortest path of $\enclose{circle}{s}$ to each of the other nodes. (Wasntme)

Nice...thank you very much! (Mmm)