グラフアルゴリズムデモ

グラフ理論の基本的なアルゴリズムのデモを表示する Java アプリケーションです。 当初は Applet として開発しましたが、 昨今は Web ブラウザでは実行しにくくなったので、ローカルアプリに書き換えました。

ランチャ	最短路問題	巡回セールスマン問題

• 使い方
• ダウンロード
• 内容

---

使い方

• ZIP をダウンロードして展開しておきます。
• GraphApplication.jar をダブルクリックするだけで起動するはずです。
• 最初にランチャが立ち上がるので、 アルゴリズム４通り×問題４通りの１６通りから選びます。
• デモ画面が開きます。"start"あるいは"step"ボタンでデモ開始です。 アルゴリズムによっては、先立って始点を選んでおきます。

---

• Java の実行環境 (JRE) が必要です。 Linuxで開発していますが、Windows, Mac のいずれでも動作します。
• JavaApplet ではありませんので、 実行には Web ブラウザもインターネット接続も不要です。
• デバッグ情報が必要な場合は、コマンドラインから次のようにして起動します。

  java -jar GraphApplication.jar

  
  

---

ダウンロード

download で配布します。通常は最新の日付の ZIP（一覧で表示される一番下のもの）をお使いください。

• GraphApplication-20YYMMDD.zip は実行ファイルです。
• GraphApplication-20YYMMDD.tar.gz はソースファイルです。
• ChangeLog は変更履歴です。

---

内容

• アルゴリズムは、次の４つあります。
  • 最小全域木問題 - Kruskal法
  • 最小全域木問題 - Prim法
  • 最短路問題 - Dijkstra法
  • 巡回セールスマン問題 - 局所探索法(2-opt, Or-opt)
  いずれも京都情報大学院大学 茨木教授の ソースコード （C言語）を Java 言語に移植して実現しました。
• データは TSPLIB95 を利用させていただきました。
• ソースコード（tar.gz）から jar を生成しなおすには Java の開発環境（JDK）が必要です。
• 著作権については、半分ほどは移植元にあると思っています。 私の追加したものについては、modified BSD と同様に扱ってください。
• オープンラボなど、研究分野紹介にご利用いただくことを想定しています。 グラフ理論の啓蒙に役立てれば幸いです。