最長パス長を求める

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
kakira
記事: 1
登録日時: 2年前

最長パス長を求める

#1

投稿記事 by kakira » 2年前

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

アバター
usao
記事: 1635
登録日時: 8年前

Re: 最長パス長を求める

#2

投稿記事 by usao » 2年前

課題の丸投げですか?

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

かずま

Re: 最長パス長を求める

#3

投稿記事 by かずま » 2年前

フォーラムルールに従って、質問してください。

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

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

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

コード:

 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: 最長パス長を求める

#4

投稿記事 by かずま » 2年前

すみません。問題を誤解していました。
スタートが 0 で、ゴールが 9 だと勝手に思い込んで今した。

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

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

返信

“C言語何でも質問掲示板” へ戻る