# Search of the Shortest Path in a Communication Network with Fuzzy Cost Functions
## 4 Dijkstra Algorithm for Type V Fuzzy Graph
### Fuzzy Dijkstra Algorithm  
Let \(\Psi(r,v)\) denote the set of all paths between \(r\) and \(v\) (\(v,r\in V\) with \(v\
eq r\)), and \(P^{*}\in\Psi(r,v)\) be the shortest path between \(r\) and \(v\). The cost of \(P^{*}\) is defined as:  
\[\widetilde{\delta}_{(r,v)}=\tilde{C}_{P^{*}(r,v)}=\left\{ \begin{array}{ll} \min_{\forall P\in\Psi(r,v)}\{\tilde{C}_{(P(r,v))}\}&\text{if }\Psi(r,v)\
eq \emptyset\\ \infty&\text{if }\Psi(r,v)=\emptyset\end{array} \right.,\]  
Then, for each vertex \(v\in V\), the algorithm defines an attribute \(\widetilde{d}\), which is an upper bound on the cost of \(P^{*}\),  
\[\widetilde{d}(v)\geq\widetilde{\delta}_{(r,v)},\]Given a vertex \(v\in V\), we will denote by \(\Gamma(v)\) the set of neighbors of \(v\), that is, the adjacent vertexes to \(v\). Moreover, we will denote by \(w(v)\) the predecessor of \(v\) in \(P^{*}\). The algorithm considers \(w(v)\) to be either a vertex of \(\Gamma(v)\) or NIL. Actually, during the execution of the algorithm, \(w(v)\) is the predecessor of \(v\) in the shortest path to \(v\) known so far. Only when the algorithm has ended, we can say that \(w(v)\) is the predecessor of \(v\) by the shortest path from \(r\) to \(v\). Every vertex is assigned a _label_, which is modified during the algorithm execution. At each stage, the label of vertex \(v\in V\) contains its predecessor in the (known so far) shortest path from \(r\) to \(v\), and the corresponding cost of this path, i.e.,  
\[ \begin{array}{ll}\text{Label}(v)=\left[\widetilde{d}(v),w(v)\right]&\text{ with}&\widetilde{d}(v)=\widetilde{d}(w(v))\,+\,\tilde{C}_{(w(v),v)}\\ &w(v):\text{(predecessor vertex of $v$ in the}\\ &\text{provisional path $P^{*}(r,v)$)}\end{array} \]  
where \(\tilde{C}_{(w(v),v)}\) is the cost of link \((w(v),v)\). At the end of the algorithm, for each vertex \(v\), \(\widetilde{d}(v)\) will coincide with \(\widetilde{\delta}_{(r,v)}\) and \(w(v)\) will be its predecessor in \(P^{*}(r,v)\). The initialization (Algorithm 1) assigns a label to every vertex in \(\tilde{G}\). The cost of the shortest path from \(r\) to any other vertex in \(v\in V\) is initialized as \(\infty\), except for \(r\), which is set to be equal to \(0\). ```
1:functionInitialize-single-source(\(\tilde{G},r,\mathfrak{C}\))
2:\(\widetilde{d}(r)\leftarrow(0,0,0)\)
3:\(w(r)\leftarrow\) NIL
4:for each vertex \(v\in V-\{r\}\)do
5:\(\widetilde{d}(v)\leftarrow\infty\)
6:endfor
7:endfunction
```  
**Algorithm 1** Initialization  
The algorithm proceeds by choosing and extracting vertexes from a set, denoted as \(H\), which is initially defined as \(V\). At each iteration, the vertex \(u\) with minimum cost is selected in \(H\) according to the ranking method described in Section 4.2. Then, the cost \(\widetilde{d}\) of the neighbors of vertex \(u\) are analyzed in the Algorithm 2 (Relaxation). Thus, the label of each neighbor \(v\in\Gamma(u)\) is updated if the path from \(r\) to \(v\) at which \(u=w(v)\) has the minimum cost at this point of the algorithm. ```
1:functionRelaxation(\(u,v,\tilde{C}_{(u,v)},\alpha\))
2:\(\widetilde{d}^{\text{\tiny{max}}}(v):=\widetilde{d}(u)\oplus\tilde{C}_{(u,v)}\)
3:if\(S^{\alpha}_{\Gamma}(\widetilde{d}(v))>S^{\alpha}_{\Gamma}(\widetilde{d}^{ \text{\tiny{max}}}(v))\)or\(\left[S^{\alpha}_{\Gamma}(\widetilde{d}(v))=S^{\alpha}_{\Gamma}(\widetilde{d}^{ \text{\tiny{max}}}(v))\)and\(\text{Me}(\widetilde{d}(v))>\text{Me}(\widetilde{d}^{\text{\tiny{max}}}(v))\right]\)then
4:\(\widetilde{d}(v)\leftarrow\widetilde{d}^{\text{\tiny{max}}}(v)\)
5:\(w(v)\gets u\)
6:endif
7:endfunction
```  
**Algorithm 2** Relaxation of \(v\)  
The algorithm ends when set \(H\) is empty. At this point, the label of each vertex \(v\) contains the cost of \(P^{*}(r,v)\) (\(\widetilde{\delta}_{(r,v)}\)) with its predecessor \(w(v)\) on this path. Following a backward procedure, the shortest path between \(r\) and each vertex is found. Algorithm 3 shows the pseudocode of the Fuzzy Dijkstra Algorithm.