dijkstra.sh

#!/usr/bin/env bash
set -eo pipefail

declare -A graph
declare -a distances


function min {
    if [[ $1 -lt $2 ]]; then
        printf "%s" "$1"
    else
        printf "%s" "$2"
    fi
}


function repeat {
    local what="$1"
    declare -i n
    n="$2"
    declare -i i
    for ((i = 0; i < n; ++i)); do
        printf "%s " "$what"
    done
}


function dijkstra {
    declare -i n
    n="$1"
    declare -a used
    distances=()
    used=($(repeat "0" "$n"))
    declare -i i
    for ((i = 0; i < n; ++i)); do
        distances+=("999999999")
    done
    distances[0]="0"
    for ((i = 0; i < n; ++i)); do
        # find min
        local j
        local distanceslen="${#distances[@]}"
        local mindist="999999999"
        local minj=0
        for ((j = 0; j < "$distanceslen"; ++j)); do
            if [[ "${used[$j]}" == 1 ]]; then
                continue
            fi
            local dist="${distances[$j]}"
            if [[ $dist -lt $mindist ]]; then
                mindist="$dist"
                minj="$j"
            fi
        done
        used[$minj]=1
        local dist="$mindist"
        local index="$minj"
        local connection_to
        for ((connection_to = 0; connection_to < n; ++connection_to)); do
            local ping_value="${graph[$index,$connection_to]}"
            distances["$connection_to"]="$(min "${distances["${connection_to}"]}" $(("$dist" + "$ping_value")))"
        done
    done
}


function main {
    declare -i n
    declare -i i
    declare -i j
    read n
    declare -a row
    for ((i = 0; i < n; ++i)); do
        read -a row
        if [[ ${#row[@]} != $n ]]; then
            echo 'Error: invalid format' >&2
            exit 1
        fi
        for ((j = 0; j < n; ++j)); do
            if [[ "${row[$j]}" -lt 0 ]]; then
                graph[$i,$j]=999999999
            else
                graph[$i,$j]="${row[$j]}"
            fi
        done
    done

    dijkstra $n

    for ((i = 0; i < n; ++i)); do
        echo "0 <-> $i: length = ${distances[$i]}"
    done
}


main "$@"