ページ 11

最長パス長を求める

Posted: 2018年10月09日(火) 16:53
by kakira
初めて投稿させていただきます
C言語の課題の一部です
各タスクからゴールまでの最長パス長を求める問題です
タスク間には先行制約があり、それぞれに処理時間が設定されている、有限無サイクル有向グラフです
左のようなグラフの場合右のような入力ファイルを読み込ませます
この時1行目は総タスク数(入り口出口ノードなし)2行目以降はタスクに関する情報で左からタスク番号、処理時間、先行タスク数を表し、それ以降は先行タスク番号です。
タスクグラフ.png

Re: 最長パス長を求める

Posted: 2018年10月09日(火) 19:59
by usao
課題の丸投げですか?

とりあえず全てのパスを列挙すればよいのではないでしょうか.

Re: 最長パス長を求める

Posted: 2018年10月10日(水) 07:35
by かずま
フォーラムルールに従って、質問してください。

自分のできる範囲のコードは書いてください。
例えば、入力データを読み込んで、確認のためそれを
表示することはできますか?

問題をよく理解するため、プログラムを書く前に
すべてのパスを書いてみて、それぞれの処理時間を見るとか。

入力の確認、すべてのパス、最長パスを表示するプログラムを
書いてみました。実行結果は次の通り。

コード:

 0 0 0
 1 1 1 0
 2 3 1 0
 3 3 1 1
 4 2 1 1
 5 6 2 3 4
 6 7 2 3 4
 7 4 2 5 6
 8 5 1 2
 9 0 2 7 8
---
  14: 0 1 3 5 7 9
  13: 0 1 4 5 7 9
  15: 0 1 3 6 7 9
  14: 0 1 4 6 7 9
   8: 0 2 8 9
---
  15: 0 1 3 6 7 9

Re: 最長パス長を求める

Posted: 2018年10月10日(水) 09:11
by かずま
すみません。問題を誤解していました。
スタートが 0 で、ゴールが 9 だと勝手に思い込んで今した。

スタートは各タスクなんですね。

しかし、ゴールはどこなんでしょうか?
きっと、そこから先に行けないところなんでしょうね。