草稿: Dijkstra’s Algorithm in Prolog

參考資料: http://en.wikipedia.org/wiki/Dijkstra’s_algorithm

定義網路:
link(‘1’, ‘2’, 7).
link(‘1’, ‘3’, 9).
link(‘1’, ‘6’, 14).
link(‘2’, ‘4’, 15).
link(‘2’, ‘3’, 10).
link(‘3’, ‘4’, 11).
link(‘3’, ‘6’, 2).
link(‘4’, ‘5’, 6).
link(‘5’, ‘6’, 9).

檢查鄰近關係:
neighboring(A, B) :- link(A, B, _).
neighboring(A, B) :- link(B, A, _).

求 A 點的鄰近點:
neighbors(A, Bs) :- setof( B, neighboring(A, B), Bs ).

求 A 點的鄰邊:
links(A, Ls) :- setof( [A, B], neighboring(A, B), Ls ).

求 A B 二點的連線權重:
weight(A, B, W) :- link(A, B, W), !.
weight(A, B, W) :- link(B, A, W), !.
weight(_, _, 0).

接著要有 tentative 路線距離,大概是要從一條已選短路線兩端都找鄰接點來測測。而主程式大概是要有三個參數,分別是未訪、已訪、及選定三個分類。先把全部的點都丟在未訪集合 (list) ,把開始點丟在選定集合。求最短路徑就是在這三個參數中按不同情況做一點點調整。這些部份就待續囉……

廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Prolog。將永久鏈結加入書籤。

One Response to 草稿: Dijkstra’s Algorithm in Prolog

  1. 引用通告: 續草稿: Dijkstra’s Algorithm in Prolog | FUNctional Programming And Others

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s