# First Request First Service Entanglement Routing Scheme for Quantum Networks
## 4 First Request First Service Entanglement Routing Scheme
### The Modified Dijkstra Algorithm  
The modified Dijkstra algorithm is proposed to find a lowest loss path from the entangled photon source to an arbitrary user (node \(i\)) with the wavelength channel \(\mathrm{ch}_{i}\). The modified Dijkstra algorithm is shown in Figure 4, which mainly consists of eight steps.  
**Step 1.** Initialize the network with \((L,P,U)=\text{Initial}(V,C,s)\), where \(L=\{l_{\kappa}^{\beta}\}\), \(P=\{p_{\kappa}^{\beta}\}\), \(U=\{u_{\kappa}^{\beta}\}\), \(\alpha=1,2,\cdots,k\) and \(\beta=1,2,\cdots,m_{\alpha}\). \(m_{\alpha}\) is the total port number of \(v_{\alpha}\), \(l_{\alpha}^{\beta}\) is the link loss from \(v_{s}\) to the \(\beta\)-th port of \(v_{\alpha}\), \(p_{\alpha}^{\beta}\) is a vector composed of the edge from \(v_{s}\) to the \(\beta\)-th port of \(v_{\alpha}\), \(u_{\alpha}^{\beta}\) represents whether the \(\beta\)-th port of node \(v_{\alpha}\) is visited (0 means unvisited and 1 means visited). If the \(\beta\)-th port of node \(\alpha\) is not directly connected to the node \(s\), \(l_{\alpha}^{\beta}=\infty\) and \(p_{\alpha}^{\beta}=\emptyset\). \(U\) is initialized by \(U_{s}^{\beta}=1\) and other elements are 0, \(\beta=1,2,\cdots,m_{s}\).  
**Step 2.** Get the next node \(q\) and its port \(\alpha\) by the operation \((q,\alpha)=\text{GPL}(L,U)\), which outputs node index \(q\) and port index \(\alpha\) with lowest loss value in the unvisited ports. Update the accessed port vector by setting \(u_{q}^{\alpha}=1\).  
**Definition 4**.: \((q,\alpha)=GPL(L,U)\)_. For \(\forall\ \delta\in\{1,2,\cdots,k\}\) and \(\varphi\in\{1,2,\cdots,m_{\alpha}\}\), find the node index \(q\) and its port index \(\alpha\), which holds \(l_{q}^{\alpha}=min\left\{l_{\delta}^{\varphi}+u_{\delta}^{\varphi}\times\infty\right\}\), where \(L=\{l_{\delta}^{\varphi}\}\) and \(U=\{u_{\delta}^{\varphi}\}\)._  
**Step 3.** If \(q=i\), output the path \(p_{i}^{\alpha}\) and stop. Otherwise, get the pass-through loss matrix of node \(v_{q}\) for the wavelength channel \(\mathrm{ch}_{i}\) as \(M=GM(v_{q},\mathrm{ch}_{i})\). if \(M=\mathcal{O}\), back to step 2.  
**Step 4.** Get the locked port \(\gamma=M[\alpha][\alpha]\). If \(\gamma=\infty\), get the \(\alpha\)-th row of \(M\) as the loss vector \(X\). Otherwise, set \(X=\{\infty\}^{m_{q}}\) and then update \(X[\gamma]\) as \(M[\alpha][\gamma]\). Afterwards, set \(r=1\) and \(\beta=1\).  
**Step 5.** Calculate the loss from the input port \(\alpha\) and different output ports of \(v_{q}\) to the port \(\beta\) of \(v_{r}\) by \(Z=X^{T}+C_{qr}[\cdot;\beta]\), where \(C_{qr}[\cdot;\beta]\) represents the \(\beta\)-th column of \(C_{qr}\). Afterwards, get the row index \(y=\min\_\text{index}(Z)\), which holds the minimum value of \(Z\).  
**Step 6.** If \(l_{q}^{\beta}+Z[y]<l_{r}^{\beta}\), update the loss \(l_{r}^{\beta}=l_{q}^{\beta}+Z[y]\), update the path \(p_{r}^{\beta}\) to \(p_{q}^{\alpha}\cup e_{yg}^{qr}\), and access to next port by \(\beta=\beta+1\). Otherwise, access to next port by \(\beta=\beta+1\).  
**Step 7.** If \(\beta>m_{r}\), update the node index \(r=r+1\) and go to step 8. Otherwise, back to step 5.  
**Step 8.** If \(r>k\), back to step 2. Otherwise, set \(\beta=1\) and back to step 5.