様式９ +-------------------------------------+----------------+----------------------+ | ｼｽﾃﾑ名(ｺｰﾄﾞ): ＡＬＧＯＰＡＫ | | システム報告書概要 | +-------------------------------------+ +----------------------+ | ﾓｼﾞｭｰﾙ名(ｺｰﾄﾞ): SHORTEST(A303) | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者･学生番号: 増沢善子 21SS1159 | 文書作成者･学生番号: 増沢善子21SS1159 | +-------------------------------------+---------------------------------------+ | 作成期間: 62/ 1/ ー / / | 文書作成期間: 62/ 2/ ー / / | +-------------------------------------+---------------------------------------+ | 親モジュール: ALGOS | 子モジュール: | +-------------------------------------+---------------------------------------+ | 講義名・課題名: 卒業研究 | 参考文献(著者名、書名、出版社、発行年)| +-------------------------------------+ | | 開発形態: 新規 | SARA BAASE, COMPUTER ALGORITHMS. | +-------------------------------------+ | | 形式: サブルーチン | ADDISON WESLSY,1978 | +-------------------------------------+---------------------------------------+ | 利用対象者: 一般 | 格納ﾒﾃﾞｨｱ形式: フロッピーディスク | +-------------------------------------+---------------------------------------+ | 目的（問題解説、機能解説−制限事項）| 格納ﾒﾃﾞｨｱ番号、ﾌｧｲﾙ名: | | SHORTEST-PATH の +---------------------------------------+ | | 記述言語・走行ＯＳ: TURBO PASCAL | | サブルーチン プログラム +---------------------------------------+ | | 走行条件（ハードウェア、ソフトウェア）| | | PC-9801 | | | | | | MS-DOS | +-------------------------------------+---------------------------------------+ | キーワード（適用分野、手法など） ： | 分類コード（ＣＲコードを使用） ： | | SHORTEST-PATH | | +-------------------------------------+---------------------------------------+ | 呼び出し法: SHORT(V,W,AGJMAT,WGTMAT,PARENT) | | | +-----------------------------------------------------------------------------+ | 操作手順(ｺﾝﾌﾟﾘｰﾄﾌﾟﾛｸﾞﾗﾑ(ﾒｲﾝﾌﾟﾛｸﾞﾗﾑ)の場合:1.システム起動手順､2.データ入出力 | | 手順と形式､3.終了手順) | | (ｻﾌﾞﾙｰﾁﾝの場合:1.呼び出し形式-引き数の並べ方-､2.親ルーチン､3.子ルー | | チン､4.その他) | | 1.SHORTを使うときは 次のような宣言が必要である。 | | | | CONST MAXNODE=9; | | | | TYPE MAT=ARRAY[1..MAXNODE,1..MAXNODE] OF INTEGER; | | | | PLIST=ARRAY[0..MAXNODE] OF INTEGER; | | | | ENTERNAL PROCEDURE SHORT(V,W:INTEGER;VAR ADJMAT,WGTMAT:MAT; | | | | VAR PARENT:PLIST); | | | | 2.（入力） V:始点ＮＯＤＥ番号 W:終点ＮＯＤＥ番号 | | | | ADJMAT: グラフのそれぞれの頂点を1から9までとする。各頂点と隣接する辺を1 | | | | とおき それ以外は0とおいた各頂点をインデックスとする２次元配列である。 | | | | WGTMAT: グラフのそれぞれの頂点を1から9までとする。各頂点と隣接する辺を | | | | 重さとおき それ以外を0とおいた各頂点をインデックスとする２次元配列である | | | | （出力） | | | | PARENT （PARENT[X],X) の和集合が求める辺集合。 | | | +-----------------------------------------------------------------------------+ 注. システム１つにつき１枚作成 必要な場合モジュール１つにつき１枚作成(ｲﾝﾀｰﾌｪｰｽ仕様書-様式１-に追加) 様式７ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | 問題解説 | +-------------------------------------+ +----------------------+ | モジュール名: SHORTEST | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 増沢 善子 | 文書作成者: 増沢 善子 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/10/25 ー / / | 文書作成期間: 60/10/25 ー / / | +-------------------------------------+---------------------------------------+ | | | G=(V,E,W)を重み付き無向グラフとする。 Wは Eから正の整数の集合切への関数 | | | | である. VをCの集合 EをこれらのCを結ぶ道の集合とする。 辺[I,J]の重み | | | | W(I,J)は辺[I,J]の長さである。 道の長さは その道に含まれる各辺の長さの和 | | | | によって定義される. これは ２頂点間の最短道を求めるのである。 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式９ +-------------------------------------+----------------+----------------------+ | ｼｽﾃﾑ名(ｺｰﾄﾞ): ＡＬＧＯＰＡＫ | | システム報告書概要 | +-------------------------------------+ +----------------------+ | ﾓｼﾞｭｰﾙ名(ｺｰﾄﾞ): CSHORTEST(P303) | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者･学生番号: 増沢善子 21SS1159 | 文書作成者･学生番号: 増沢善子21SS1159 | +-------------------------------------+---------------------------------------+ | 作成期間: 62/ 1/ ー / / | 文書作成期間: 62/ 2/ ー / / | +-------------------------------------+---------------------------------------+ | 親モジュール: ALGOS | 子モジュール: | +-------------------------------------+---------------------------------------+ | 講義名・課題名: 卒業研究 | 参考文献(著者名、書名、出版社、発行年)| +-------------------------------------+ | | 開発形態: 新規 | SARA BAASE,COMPUTER ALGORITHMS. | +-------------------------------------+ | | 形式: コンプリート | ADDISON WESLEY,1978 | +-------------------------------------+---------------------------------------+ | 利用対象者: 一般 | 格納ﾒﾃﾞｨｱ形式: フロッピーディスク | +-------------------------------------+---------------------------------------+ | 目的（問題解説、機能解説−制限事項）| 格納ﾒﾃﾞｨｱ番号、ﾌｧｲﾙ名: | | コンプリート プログラム +---------------------------------------+ | | 記述言語・走行ＯＳ: TURBO PASCAL | | +---------------------------------------+ | | 走行条件（ハードウェア、ソフトウェア）| | | PC-9801 | | | | | | MS-DOS | +-------------------------------------+---------------------------------------+ | キーワード（適用分野、手法など） ： | 分類コード（ＣＲコードを使用） ： | | SHORTEST-PATH | | +-------------------------------------+---------------------------------------+ | 呼び出し法: CSHORT | | | +-----------------------------------------------------------------------------+ | 操作手順(ｺﾝﾌﾟﾘｰﾄﾌﾟﾛｸﾞﾗﾑ(ﾒｲﾝﾌﾟﾛｸﾞﾗﾑ)の場合:1.システム起動手順､2.データ入出力 | | 手順と形式､3.終了手順) | | (ｻﾌﾞﾙｰﾁﾝの場合:1.呼び出し形式-引き数の並べ方-､2.親ルーチン､3.子ルー | | チン､4.その他) | | 　　　　　　　 | | | | 　　　　　　　　　　　　　　　　　　　　　　　　　 | | | | 1. >CSHORT | | | | 2.(入力）ファイル名ADJ4 WGT4 のテキストファイルに次のデータを入れておく。 | | | | ADJ4 1から9までをノード番号とし ノード番号をインデックスとする２次元配列 | | | | ノードiからノードjに辺があれば(i,j)=1 辺がなければ(i,j)=0 とする。 | | | | WGT4 1から9までをノード番号とし ノード番号をインデックスとする２次元配列 | | | | ノードiからノードjに辺があれば(i,j)= 重さ 辺がなければ(i,j)=0 とする。 | | | | （出力） | | | | SHORTEST-PATH を構成するEDREがNODEに対して順次出力される。 | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 注. システム１つにつき１枚作成 必要な場合モジュール１つにつき１枚作成(ｲﾝﾀｰﾌｪｰｽ仕様書-様式１-に追加) 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: SHORTEST | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 増 沢 善 子 | 文書作成者: 増 沢 善 子 | +-------------------------------------+---------------------------------------+ | 作成期間: 61/1 / ー 61/2 / | 文書作成期間: 61/1 / ー 61/2 / | +-------------------------------------+---------------------------------------+ | | | ++-------++ +-----+ ++-------++ +---------+ | | !!module !! +const + !!maxnode!! !9 ! | | !!shortp !!-!--+ +----!! !!----! ! | | !! !! ! + + !! !! ! ! | | ++-------++ ! +-----+ ++-------++ +---------+ | | ! | | ! +-----+ ++-------++ +--------++ +---------+ | | ! +type + !!mat !! !array [ !! !integer ! | | !--+ +-!--!! !!----!1 .. !!----! ! | | ! + + ! !! !! !maxnode !! ! ! | | ! +-----+ ! ++-------++ !, 1 .. !! +---------+ | | ! ! !maxnode !! | | ! ! !] !! | | ! ! ! !! | | ! ! ! !! | | ! ! ! !! | | ! ! +--------++ | | ! ! | | ! ! ++-------++ +--------++ +---------+ | | ! ! !!plist !! !array [ !! !integer ! | | ! !--!! !!----!0 .. !!----! ! | | ! ! !! !! !maxnode !! ! ! | | ! ! ++-------++ +--------++ +---------+ | | ! ! | | ! ! ++-------++ +---------+ | | ! ! !!nodeptr!! !^ node ! | | ! !--!! !!----! ! | | ! ! !! !! ! ! | | ! ! ++-------++ +---------+ | | ! ! | | ! ! ++-------++ +------++ +-------+ | | ! ! !!node !! !record ++ +vtx + | | ! ---!! !!----! ++-!--! !---| | ! !! !! ! ++ ! + + | | ! ++-------++ +------++ ! +-------+ | | ! ! | | ! ! +-------+ | | ! ! +wgt + | | ! !--! !---| | ! ! + + | | ! ! +-------+ | | ! ! | | ! ! +-------+ | | ! ! +link + | | ! ---! !---| | ! + + | | ! +-------+ | | ! | | ! ++-------++ +-----+ +-------+ +---------+ | | ! !!procedu!! +paramet+ +v , w + !integer ! | | ---!!re !!-!--+ er +-!--! !----! ! | | !!short !! ! + + ! + + ! ! | | ++-------++ ! +-----+ ! +-------+ +---------+ | | ! ! | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: SHORTEST | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 増 沢 善 子 | 文書作成者: 増 沢 善 子 | +-------------------------------------+---------------------------------------+ | 作成期間: 61/1 / ー 61/2 / | 文書作成期間: 61/1 / ー 61/2 / | +-------------------------------------+---------------------------------------+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +---------+ | | !integer ! | |---! ! | | ! ! | | +---------+ | | | | +---------+ | | !integer ! | |---! ! | | ! ! | | +---------+ | | | | ++-------++ | | !!nodeptr!! | |---!! !! | | !! !! | | ++-------++ | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: SHORTEST | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 増 沢 善 子 | 文書作成者: 増 沢 善 子 | +-------------------------------------+---------------------------------------+ | 作成期間: 61/1 / ー 61/2 / | 文書作成期間: 61/1 / ー 61/2 / | +-------------------------------------+---------------------------------------+ | ! ! | | ! ! +-------+ ++-------++ | | ! ! +var + !!mat !! | | ! !--!adjmat , !----!! !! | | ! ! +wgtmat + !! !! | | ! ! +-------+ ++-------++ | | ! ! | | ! ! +-------+ ++-------++ | | ! ! +var + !!plist !! | | ! ---!parent !----!! !! | | ! + + !! !! | | ! +-------+ ++-------++ | | ! | | ! +-----+ +-------+ ++-------++ | | ! +var + +ptr + !!nodeptr!! | | !--+ +-!--! !----!! !! | | ! + + ! + + !! !! | | ! +-----+ ! +-------+ ++-------++ | | ! ! | | ! ! +-------+ +---------+ | | ! ! +e1 , e2 + !integer ! | | ! !--! !----! ! | | ! ! + + ! ! | | ! ! +-------+ +---------+ | | ! ! | | ! ! +-------+ +---------+ | | ! ! +x , y , + !integer ! | | ! !--!i , j !----! ! | | ! ! + + ! ! | | ! ! +-------+ +---------+ | | ! ! | | ! ! +-------+ +--------++ | | ! ! +v2link + !array [ !! | | ! !--! !----!0 .. !!---| | ! ! + + !maxnode !! | | ! ! +-------+ +--------++ | | ! ! | | ! ! +-------+ +--------++ | | ! ! +vset + !array [ !! | | ! !--! !----!0 .. !!---| | ! ! + + !maxnode !! | | ! ! +-------+ +--------++ | | ! ! | | ! ! +-------+ +--------++ | | ! ! +adjlist + !array [ !! | | ! !--! !----!0 .. !!---| | ! ! + + !maxnode !! | | ! ! +-------+ +--------++ | | ! ! | | ! ! +-------+ +---------+ | | ! ! +ecount + !integer ! | | ! !--! !----! ! | | ! ! + + ! ! | | ! ! +-------+ +---------+ | | ! ! | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: SHORTEST | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 増 沢 善 子 | 文書作成者: 増 沢 善 子 | +-------------------------------------+---------------------------------------+ | 作成期間: 61/1 / ー 61/2 / | 文書作成期間: 61/1 / ー 61/2 / | +-------------------------------------+---------------------------------------+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +---------+ | | !integer ! | |---! ! | | ! ! | | +---------+ | | | | +---------+ | | !integer ! | |---! ! | | ! ! | | +---------+ | | | | ++-------++ | | !!nodeptr!! | |---!! !! | | !! !! | | ++-------++ | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: SHORTEST | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 増 沢 善 子 | 文書作成者: 増 沢 善 子 | +-------------------------------------+---------------------------------------+ | 作成期間: 61/1 / ー 61/2 / | 文書作成期間: 61/1 / ー 61/2 / | +-------------------------------------+---------------------------------------+ | ! ! | | ! ! +-------+ ++-------++ | | ! ! +a , b , + !!nodeptr!! | | ! !--!c , e , !----!! !! | | ! ! !f , g , ! !! !! | | ! ! !h , ! ++-------++ | | ! ! !nowptr , ! | | ! ! !newptr ! | | ! ! ! ! | | ! ! ! ! | | ! ! + + | | ! ! +-------+ | | ! ! | | ! ! +-------+ +--------++ | | ! ! +d + !array [ !! | | ! ---! !----!1 .. !!---| | ! + + !maxnode !! | | ! +-------+ +--------++ | | ! | | ! ++-------++ +---------+ | | ! !!functio!! !integer ! | | !--!!n !!-!--! ! | | ! !!min_d !! ! ! ! | | ! ++-------++ ! +---------+ | | ! ! | | ! ! +-----+ +-------+ | | ! ! +var + +min , i + | | ! !--+ +----!, !---| | ! ! + + +min_idx + | | ! ! +-----+ +-------+ | | ! ! | | ! ! +---------+ | | ! ! !min := ! | | ! -!-!9999 ; ! | | ! ! !min_idx ! | | ! ! !:= ! | | ! ! !maxnode +! | | ! ! !1 ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! +---------+ | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: SHORTEST | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 増 沢 善 子 | 文書作成者: 増 沢 善 子 | +-------------------------------------+---------------------------------------+ | 作成期間: 61/1 / ー 61/2 / | 文書作成期間: 61/1 / ー 61/2 / | +-------------------------------------+---------------------------------------+ | | | | | | | | | | | | | | | | | | | | | | | | | | | +---------+ | | !integer ! | |---! ! | | ! ! | | +---------+ | | | | | | | | | | | | | | | | +---------+ | | !integer ! | |---! ! | | ! ! | | +---------+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: SHORTEST | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 増 沢 善 子 | 文書作成者: 増 沢 善 子 | +-------------------------------------+---------------------------------------+ | 作成期間: 61/1 / ー 61/2 / | 文書作成期間: 61/1 / ー 61/2 / | +-------------------------------------+---------------------------------------+ | ! ! ! | | ! ! +--------++ +-------+ | | ! ! !for i !! !if vset + | | ! ! !:= 1 to !!----![ i ] = +---| | ! ! !maxnode !! !2 + | | ! ! ! !! +-------+ | | ! ! ! !! | | ! ! ! !! | | ! ! ! !! | | ! ! ! !! | | ! ! ! !! | | ! ! +--------++ | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! +---------+ | | ! ! !min_d := ! | | ! !-!min_idx ! | | ! ! ! | | ! +---------+ | | ! | | ! ++-------++ +-----+ +-------+ | | ! !!procedu!! +paramet+ +x + | | !--!!re !!-!--+ er +----! !---| | ! !!remove !! ! + + + + | | ! ++-------++ ! +-----+ +-------+ | | ! ! | | ! ! +-----+ +-------+ | | ! ! +var + +link + | | ! !--+ +----! !---| | ! ! + + + + | | ! ! +-----+ +-------+ | | ! ! | | ! ! +---------+ | | ! ! !link := ! | | ! -!-!0 ! | | ! ! ! ! | | ! ! +---------+ | | ! ! ! | | ! ! +--------++ +---------+ | | ! ! !while ( !! !link := ! | | ! ! !v2link !!----!v2link [ ! | | ! ! ![ link !! !link ] ! | | ! ! !] = x ) !! +---------+ | | ! ! !or ( !! | | ! ! !v2link [!! | | ! ! !link ] !! | | ! ! != 0 ) !! | | ! ! ! !! | | ! ! +--------++ | | ! ! ! | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: SHORTEST | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 増 沢 善 子 | 文書作成者: 増 沢 善 子 | +-------------------------------------+---------------------------------------+ | 作成期間: 61/1 / ー 61/2 / | 文書作成期間: 61/1 / ー 61/2 / | +-------------------------------------+---------------------------------------+ | T: T: | | +-------+ +---------+ | | !if d [ + !min := d ! | |---!i ] < +----![ i ] ; ! | | !min + !min_idx ! | | +-------+ !:= i ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | +---------+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | +---------+ | | !integer ! | |---! ! | | ! ! | | +---------+ | | | | +---------+ | | !integer ! | |---! ! | | ! ! | | +---------+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: SHORTEST | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 増 沢 善 子 | 文書作成者: 増 沢 善 子 | +-------------------------------------+---------------------------------------+ | 作成期間: 61/1 / ー 61/2 / | 文書作成期間: 61/1 / ー 61/2 / | +-------------------------------------+---------------------------------------+ | ! ! ! T: | | ! ! +-------+ +---------+ | | ! ! !if + !v2link [ ! | | ! !-!v2link [ +----!link ] ! | | ! !link ] ! !:= v2link! | | ! != x ! ![ v2link ! | | ! ! ! ![ link ] ! | | ! ! ! !] ! | | ! ! ! ! ! | | ! ! + ! ! | | ! ! + ! ! | | ! +-------+ +---------+ | | ! | | ! ++-------++ +-----+ +-------+ | | ! !!procedu!! +var + +root , + | | !--!!re !!-!--+ +-!--!ptr !---| | ! !!makeadj!! ! + + ! + + | | ! ++-------++ ! +-----+ ! +-------+ | | ! ! ! | | ! ! ! +-------+ | | ! ! ! +i , j + | | ! ! ---! !---| | ! ! + + | | ! ! +-------+ | | ! ! | | ! ! +--------++ +---------+ | | ! ! !for i !! !root := ! | | ! ---!:= 1 to !!--!-!nil ! | | ! !maxnode !! ! ! ! | | ! ! !! ! +---------+ | | ! ! !! ! ! | | ! ! !! ! ! | | ! ! !! ! ! | | ! ! !! ! ! | | ! ! !! ! ! | | ! +--------++ ! ! | | ! ! ! | | ! ! +--------++ | | ! ! !for j !! | | ! ! !:= 1 to !!---| | ! ! !maxnode !! | | ! ! ! !! | | ! ! ! !! | | ! ! ! !! | | ! ! ! !! | | ! ! ! !! | | ! ! ! !! | | ! ! +--------++ | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: SHORTEST | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 増 沢 善 子 | 文書作成者: 増 沢 善 子 | +-------------------------------------+---------------------------------------+ | 作成期間: 61/1 / ー 61/2 / | 文書作成期間: 61/1 / ー 61/2 / | +-------------------------------------+---------------------------------------+ | | | | | | | | | | | | | | | | | | | | | | | | | | | ++-------++ | | !!nodeptr!! | |---!! !! | | !! !! | | ++-------++ | | | | +---------+ | | !integer ! | |---! ! | | ! ! | | +---------+ | | | | | | | | | | | | | | | | | | | | | | | | | | T: | | +-------+ +---------+ | | !if + !new ( ! | |---!adjmat [ +--!-!ptr ) ! | | !i , j ] ! ! ! ! | | != 1 ! ! +---------+ | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! + ! ! | | ! + ! ! | | +-------+ ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: SHORTEST | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 増 沢 善 子 | 文書作成者: 増 沢 善 子 | +-------------------------------------+---------------------------------------+ | 作成期間: 61/1 / ー 61/2 / | 文書作成期間: 61/1 / ー 61/2 / | +-------------------------------------+---------------------------------------+ | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! ! | | ! ! +---------+ | | ! ! !adjlist ! | | ! !-![ i ] := ! | | ! !root ! | | ! +---------+ | | ! | | ! ++-------++ | | ! !!makeadj!! | | -!-!! !! | | ! !! !! | | ! ++-------++ | | ! ! | | ! +---------+ | | ! !vset [ v ! | | ! !] := 1 ; ! | | ! !x := v ; ! | | ! !d [ v ] ! | | ! !:= 0 ; ! | | ! !v2link [ ! | | ! !0 ] := 0 ! | | ! ! ! | | ! ! ! | | ! +---------+ | | ! ! | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: SHORTEST | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 増 沢 善 子 | 文書作成者: 増 沢 善 子 | +-------------------------------------+---------------------------------------+ | 作成期間: 61/1 / ー 61/2 / | 文書作成期間: 61/1 / ー 61/2 / | +-------------------------------------+---------------------------------------+ | ! ! | | ! +--------++ +---------+ | | ! !with !! !vtx := j ! | | ! !ptr ^ !!----!; ! | | ! ! !! !wgt := ! | | ! +--------++ !wgtmat [ ! | | ! ! !i , j ] ! | | ! ! !; ! | | ! ! !link := ! | | ! ! !root ! | | ! ! ! ! | | ! ! +---------+ | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! +---------+ | | ! !root := ! | | !-!ptr ! | | ! ! | | +---------+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: SHORTEST | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 増 沢 善 子 | 文書作成者: 増 沢 善 子 | +-------------------------------------+---------------------------------------+ | 作成期間: 61/1 / ー 61/2 / | 文書作成期間: 61/1 / ー 61/2 / | +-------------------------------------+---------------------------------------+ | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! ! | | ! +--------++ +---------+ | | ! !for i !! !vset [ i ! | | ! !:= 2 to !!----!] := 3 ! | | ! !maxnode !! ! ! | | ! ! !! +---------+ | | ! ! !! | | ! ! !! | | ! ! !! | | ! ! !! | | ! ! !! | | ! +--------++ | | ! ! | | ! +--------++ +---------+ | | ! !while x !! !ptr := ! | | !-!<> w !!--!-!adjlist [! | | ! !! ! !x ] ! | | +--------++ ! +---------+ | | ! ! | | ! +--------++ +---------+ | | ! !while !! !y := ptr ! | | ! !ptr <> !!--!-!^ . vtx ! | | ! !nil !! ! ! ! | | ! +--------++ ! +---------+ | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: SHORTEST | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 増 沢 善 子 | 文書作成者: 増 沢 善 子 | +-------------------------------------+---------------------------------------+ | 作成期間: 61/1 / ー 61/2 / | 文書作成期間: 61/1 / ー 61/2 / | +-------------------------------------+---------------------------------------+ | ! ! ! ! | | ! ! ! +-------+ | | ! ! ! !if ( + | | ! ! ! !vset [ y +---| | ! ! ! !] = 2 ) ! | | ! ! ! !and ( d ! | | ! ! ! ![ x ] + ! | | ! ! ! !ptr ^ . ! | | ! ! ! !wgt < d ! | | ! ! ! ![ y ] ) ! | | ! ! ! ! ! | | ! ! ! ! ! | | ! ! ! ! ! | | ! ! ! ! ! | | ! ! ! ! ! | | ! ! ! ! + | | ! ! ! ! + | | ! ! ! +-------+ | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! +-------+ | | ! ! ! !if vset + | | ! ! ! ![ y ] = +---| | ! ! ! !3 + | | ! ! ! +-------+ | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | +-----------------------------------------------------------------------------+ +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: SHORTEST | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 増 沢 善 子 | 文書作成者: 増 沢 善 子 | +-------------------------------------+---------------------------------------+ | 作成期間: 61/1 / ー 61/2 / | 文書作成期間: 61/1 / ー 61/2 / | +-------------------------------------+---------------------------------------+ | T: | | +---------+ | | !parent [ ! | |---!y ] := x ! | | !; ! | | !d [ y ] ! | | !:= d [ x ! | | !] + ptr ! | | !^ . wgt ! | | ! ! | | ! ! | | +---------+ | | | | | | | | | | | | | | | | | | | | - | | | | | | T: | | +---------+ | | !vset [ y ! | |---!] := 2 ; ! | | !v2link [ ! | | !y ] := ! | | !v2link [ ! | | !0 ] ; ! | | !v2link [ ! | | !0 ] := y ! | | !; ! | | !parent [ ! | | !y ] := x ! | | !; ! | | !d [ y ] ! | | !:= d [ x ! | | !] + ptr ! | | +---------+ | | | | | | | | | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: SHORTEST | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 増 沢 善 子 | 文書作成者: 増 沢 善 子 | +-------------------------------------+---------------------------------------+ | 作成期間: 61/1 / ー 61/2 / | 文書作成期間: 61/1 / ー 61/2 / | +-------------------------------------+---------------------------------------+ | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! ! | | ! ! ! +---------+ | | ! ! ! !ptr := ! | | ! ! !-!ptr ^ . ! | | ! ! !link ! | | ! ! +---------+ | | ! ! T: | | ! +-------+ +-------+ | | ! !if + +writeln+ | | ! !v2link [ +--!- !( ! | | ! !0 ] = 0 ! ! !'no pat! | | ! ! ! ! !h to ' ! | | ! ! ! ! !, w ! | | ! ! ! ! !) ! | | ! ! ! ! ! ! | | ! ! + ! ! ! | | ! ! + ! + + | | ! +-------+ ! +-------+ | | ! ! ! ! | | ! ! ! ++-------++ | | ! ! ! !!exit !! | | ! ! !-!! !! | | ! ! !! !! | | ! ! ++-------++ | | ! ! | | ! +---------+ | | ! !y := ! | | ! !min_d ! | | ! ! ! | | ! +---------+ | | ! ! | | ! ++-------++ | | ! !!remove !! | | ! !!( y ) !! | | ! !! !! | | ! ++-------++ | | ! ! | | ! +---------+ | | ! !vset [ y ! | | !-!] := 1 ; ! | | !x := y ! | | +---------+ | | | +-----------------------------------------------------------------------------+