Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
Download

📚 The CoCalc Library - books, templates and other resources

132930 views
License: OTHER
Tweet
Share
Share
1
\documentclass{article}

2
\usepackage[pdftex,active,tightpage]{preview}

3
\setlength\PreviewBorder{2mm}

4


5
\usepackage[utf8]{inputenc} % this is needed for umlauts

6
\usepackage[ngerman]{babel} % this is needed for umlauts

7
\usepackage[T1]{fontenc}    % this is needed for correct output of umlauts in pdf

8
\usepackage{amssymb,amsmath,amsfonts} % nice math rendering

9
\usepackage{braket} % needed for \Set

10
\usepackage{caption}

11
\usepackage{algorithm}

12
\usepackage[noend]{algpseudocode}

13


14
\DeclareCaptionFormat{myformat}{#3}

15
\captionsetup[algorithm]{format=myformat}

16


17
\begin{document}

18
\begin{preview}

19
    \begin{algorithm}[H]

20
        \begin{algorithmic}

21
        \Require

22
        \Statex Graph $G = (V, E)$

23
        \Statex Weight from node $i$ to node $j$: $g_{ij} \in \mathbb{R}_0^+$

24
        \Statex Starting node $s \in V$

25
        \Statex End node $t \in V$

26
        \Statex Lower bound to get from node $j$ to $t$: $h_j$ (default: $h_j = 0$)

27
        \Statex Upper bound to get from node $j$ to $t$: $m_j$ (default: $m_j = \infty$)

28
        \Procedure{LabelCorrection}{$G$, $s$, $t$, $h$, $m$}

29
            \State $d_s \gets 0$

30
            \State $d_i \gets \infty \quad \forall i \neq s$ \Comment{Distance of node $i$ from $s$}

31
            \State $u \gets \infty$ \Comment{Distance from $s$ to $t$}

32
            \State $K \gets \{s\}$ \Comment{Choose some datastructure here}

33
            \While{$K$ is not empty}

34
                \State $v \gets K.pop()$

35
                \For{child $c$ of $v$}

36
                    \If{$d_v + g_{vc} + h_c < \min(d_c, u)$}

37
                        \State $d_c \gets d_v + g_{vc}$

38
                        \State $c.parent \gets v$

39
                        \If{$c \neq t$ and $c \notin K$}

40
                            \State $K.insert(c)$

41
                        \EndIf

42
                        \If{$c = t$}

43
                            \State $u \gets d_v + g_{vt}$

44
                        \EndIf

45
                    \EndIf

46
                    \State $u \gets \min (u, d_c + m_c)$

47
                \EndFor

48
            \EndWhile

49
            \Return $u, t$

50
        \EndProcedure

51
        \end{algorithmic}

52
    \caption{Label correction algorithm: Find shortest path}

53
    \label{alg:label-correction-algorithm}

54
    \end{algorithm}

55
\end{preview}

56
\end{document}

57


58