トロピカル最短経路 https://qiita.com/lotz/items/094bffd77b24e37bf20e

Tropical.cs

using System;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Linq;

namespace tropical
{
    class Program
    {
        enum NODE
        {
            A,
            B,
            C,
            D,
        }

        enum EDGE
        {
            A_B,
            A_C,
            B_C,
            B_D,
            C_D,
            D_A,
        }

        static void Main(string[] args)
        {
            const int node_count = 4;
            var nodes = new Dictionary<NODE, Node>(node_count) {
                [NODE.A] = new Node("a"),
                [NODE.B] = new Node("b"),
                [NODE.C] = new Node("c"),
                [NODE.D] = new Node("d"),
            };

            var edges = new Dictionary<EDGE, Edge> {
                [EDGE.A_B] = new Edge(2, nodes[NODE.A], nodes[NODE.B]),
                [EDGE.A_C] = new Edge(4, nodes[NODE.A], nodes[NODE.C]),
                [EDGE.B_C] = new Edge(1, nodes[NODE.B], nodes[NODE.C]),
                [EDGE.B_D] = new Edge(9, nodes[NODE.B], nodes[NODE.D]),
                [EDGE.C_D] = new Edge(5, nodes[NODE.C], nodes[NODE.D]),
                [EDGE.D_A] = new Edge(3, nodes[NODE.D], nodes[NODE.A]),
            };

            var tropical_edges = new TropicalRoute[node_count, node_count] {
                { TropicalRoute.Infinity, edges[EDGE.A_B],        edges[EDGE.A_C],        TropicalRoute.Infinity, },
                { TropicalRoute.Infinity, TropicalRoute.Zero,     edges[EDGE.B_C],        edges[EDGE.B_D],        },
                { TropicalRoute.Infinity, TropicalRoute.Infinity, TropicalRoute.Infinity, edges[EDGE.C_D],        },
                { edges[EDGE.D_A],        TropicalRoute.Infinity, TropicalRoute.Infinity, TropicalRoute.Infinity, },
            };

            TropicalRoute[,] matrix_mul(TropicalRoute[,] l, TropicalRoute[,] r)
            {
                var result = new TropicalRoute[node_count, node_count];
                for (var i = 0; i < node_count; ++i)
                {
                    for (var j = 0; j < node_count; ++j)
                    {
                        // トロピカル加法の単位元は ∞
                        result[i, j] = TropicalRoute.Infinity;
                        for (var k = 0; k < node_count; ++k)
                        {
                            result[i, j] += l[i, k] * r[k, j];
                        }
                    }
                }
                return result;
            }

            var calc = tropical_edges;
            for (var i = 0; i < 3; ++i)
            {
                calc = matrix_mul(calc, calc);
            }

            for (var i = 0; i < node_count; ++i)
            {
                var cost = Enumerable.Range(0, node_count)
                    .Select(j => calc[i, j].Cost);

                Console.WriteLine(string.Join(", ", cost.Select(e => $"{e, 2}")));
            }

            for (var i = 0; i < node_count; ++i)
            {
                for (var j = 0; j < node_count; ++j)
                {
                    var result = calc[i, j];

                    Console.WriteLine($"\n{nodes[(NODE)i].Name} -> {nodes[(NODE)j].Name} の経路");
                    if (result.IsInfinity)
                    {
                        Console.WriteLine("行けません");
                        continue;
                    }
                    Console.WriteLine($"コスト: {result.Cost}");
                    foreach (var e in result.Paths)
                    {
                        var node = e.Edges.Select(x => x.End)
                            .Prepend(e.Edges[0].Start);

                        Console.WriteLine(string.Join(" -> ", node.Select(x => x.Name)));
                    }
                }
            }
        }
    }

    public class Node
    {
        public string Name { get; }

        public Node(string name)
        {
            this.Name = name;
        }
    }

    public class Edge
    {
        public uint Cost { get; }

        public Node Start { get; }

        public Node End { get; }

        public Edge(uint cost, Node start, Node end)
        {
            this.Cost = cost;
            this.Start = start;
            this.End = end;
        }
    }

    public struct Path
    {
        public uint Cost { get; }

        public IReadOnlyList<Edge> Edges => this.edges; 

        private ImmutableList<Edge> edges { get; }
        
        private Path(uint cost, ImmutableList<Edge> edges)
        {
            this.Cost = cost;
            this.edges = edges;
        }

        public static implicit operator Path(Edge edge)
            => new Path(edge.Cost, ImmutableList.Create(edge));

        public static Path operator +(Path l, Path r)
            => new Path(l.Cost + r.Cost, l.edges.AddRange(r.edges));
    }

    public struct TropicalRoute
    {
        public uint Cost { get; }

        public IReadOnlyList<Path> Paths => this.paths;

        /// <summary>
        /// 同じコストの複数ルートを持てるようにする
        /// </summary>
        private ImmutableList<Path> paths { get; }

        private TropicalRoute(uint cost, ImmutableList<Path> paths)
        {
            this.Cost = cost;
            this.paths = paths;
        }

        public static implicit operator TropicalRoute(Path path)
            => new TropicalRoute(path.Cost, ImmutableList.Create(path));

        public static implicit operator TropicalRoute(Edge edge)
            => (Path)edge;

        public static TropicalRoute Zero { get; }
            = new TropicalRoute(0, ImmutableList<Path>.Empty);

        public bool IsZero => this.Cost == 0;

        public static TropicalRoute Infinity { get; }
            = new TropicalRoute(uint.MaxValue, null);

        public bool IsInfinity => this.paths == null;

        /// <summary>
        /// トロピカル加算
        /// コスト小さい方返す
        /// 同じときは複数経路にまとめる
        /// </summary>
        public static TropicalRoute operator +(TropicalRoute l, TropicalRoute r)
        {
            if (r.IsInfinity || l.IsZero)
            {
                return l;
            }

            if (l.IsInfinity || r.IsZero)
            {
                return r;
            }

            if (l.Cost != r.Cost)
            {
                return l.Cost < r.Cost ? l : r;
            }

            var list = l.paths.AddRange(r.paths);
            return new TropicalRoute(l.Cost, list);
        }

        /// <summary>
        /// トロピカル乗算
        /// 経路を加算する
        /// </summary>
        public static TropicalRoute operator *(TropicalRoute l, TropicalRoute r)
        {
            if (l.IsInfinity || r.IsInfinity)
            {
                return Infinity;
            }

            if (r.IsZero)
            {
                return l;
            }

            if (l.IsZero)
            {
                return r;
            }

            var list = l.Paths
                .SelectMany(e => r.Paths.Select(x => e + x))
                .ToImmutableList();
            return new TropicalRoute(l.Cost + r.Cost, list);
        }
    }
}