このディレクトリの索引


ダイクストラ法による最短距離探索(_出発点,_距離,_最短経路,_確定集合) :-
        _確定集合_1 = [[_出発点,0,[_出発点]]],
        初期の未確定集合を得る(_出発点,_未確定集合),
        ダイクストラ法による最短距離探索(_確定集合_1,_未確定集合,_確定集合).

初期の未確定集合を得る(_出発点,_初期未確定集合) :-
        setof([_出発点,9999,[]],[_点,_隣接点,_距離,_出発点] ^ (
                    経路(_点,_隣接点,_距離),
                    \+(_点 = _出発点)),
                _初期未確定集合).

ダイクストラ法による最短距離探索(_確定集合,[],_確定集合).
ダイクストラ法による最短距離探索([[_直前に確定した点,_距離,_経路]|R],_未確定集合_1,_確定集合) :-
        直前に確定した点から全ての隣接点の未確定集合を更新する(_直前に確定した点,_距離,_経路,_未確定集合_1,_未確定集合_2),
        未確定集合から最小距離点を抜き取る(_未確定集合_2,_最小距離点,_最小距離,_最小距離点の経路,_未確定集合_3),
        確定集合に追加(_最小距離点,_最小距離,_最小経路点の経路,[[_直前に確定した点,_距離,_経路]|R],_確定集合_2),
        ダイクストラ法による最短距離探索(_確定集合_2,_未確定集合_3,_確定集合).

直前に確定した点から全ての隣接点の未確定集合を更新する(_直前に確定した点,_距離,_経路,_未確定集合_1,_未確定集合_2) :-
        findall([_隣接点,_距離],
                    隣接点を得る(_直前に確定した点,_未確定集合,_隣接点,_距離),
                LL),
        直前に確定した点から全ての隣接点の未確定集合を更新する(_直前に確定した点,_距離,_経路,LL,_未確定集合_1,_未確定集合_2).


直前に確定した点から全ての隣接点の未確定集合を更新する(_直前に確定した点,_直前に確定した点までの距離,_直前に確定した点までの経路,[[_隣接点,_距離]|R],_未確定集合_1,_未確定集合_2) :-
        未確定集合の更新(_直前に確定した点,_直前に確定した点までの距離,_直前に確定した点までの経路,_隣接点,_距離,_未確定集合_1,_未確定集合_3),
        直前に確定した点から全ての隣接点の未確定集合を更新する(_直前に確定した点,_直前に確定した点までの距離,_直前に確定した点までの経路,R,_未確定集合_3,_未確定集合_2).

隣接点を得る(_直前に確定した点,_未確定集合,_隣接点,_距離) :-
        経路(_直前に確定した点,_隣接点,_距離),
        member([_隣接点,_,_],_未確定集合).

未確定集合の更新(_直前に確定した点,_直前に確定した点までの距離,_直前に確定した点までの経路,_隣接点,_距離,_未確定集合_1,_未確定集合_2) :-
        _距離_2 is _直前に確定した点までの距離 + _距離,
        append(L1,[[_隣接点,_距離_1,_経路_1]|L2],_未確定集合_1),
        _距離_1 > _距離_2,
        append(L1,[[_隣接点,_距離_1,[_隣接点|_直前に確定した点までの経路]]|L2],_未確定集合_2),!.
未確定集合の更新(_,_,_,_,_,_未確定集合,_未確定集合).

未確定集合から最小距離点を抜き取る(_未確定集合_1,_最小距離点,_最小距離,_最小距離点の経路,_未確定集合_2) :-
        append(L1,[[_最小距離点,_最小距離,_最小距離の経路]|L2],_未確定集合_1),
        forall(member([_,_距離_1,_],L1),_距離_1 >= _最小距離),
        forall(member([_,_距離_2,_],L1),_距離_2 >= _最小距離),
        append(L1,L2,_未確定集合_2),!.

確定集合に追加(_点,_距離,_経路,_確定集合_1,[[_点,_距離,_経路]|_確定集合_1]).