shortest-paths.bash

#!/bin/bash
jq -Rr 'split(",")' | jq -scr '

    def table_to_edges: . as [$src, $dst, $weight] |
        {$src, $dst, weight: $weight | tonumber};

    def edges_to_table: . as {$src, $dst, $weight} |
        [$src, $dst, $weight];

    def graph_to_edges:
        . as $graph |
        to_entries[] as {key: $src, value: $edges} |
        $edges | to_entries[] as {key: $dst, value: $weight} |
        {$src, $dst, $weight};

    def edges_to_graph: reduce .[] as {$src, $dst, $weight} ({};
        . + {($src): ((.[$src] // {}) + {
            ($dst): [
                (.[$src][$dst] // infinite),
                $weight
            ] | min,
        })}
    );

    def coedges: . as {$src, $dst, $weight} | {src: $dst, dst: $src, $weight};

    def cograph: [graph_to_edges | coedges] | edges_to_graph;

    def shortest_paths: reduce to_entries[] as {key: $mid, value: $edges}
    (
        cograph;
        . as $cograph |
        [
            ($cograph | graph_to_edges),
            (
                ($cograph[$mid] // {}) |
                to_entries[] as {key: $dst, value: $hemi} |
                $edges |
                to_entries[] as {key: $src, value: $demi} |
                {$src, $dst, weight: ($hemi + $demi)}
            )
        ] |
        edges_to_graph
    );

    [.[] | table_to_edges] |
    edges_to_graph |
    shortest_paths |
    cograph |
    graph_to_edges |
    edges_to_table |
    @tsv

' | sort -n