協力お願いします

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
jvhdoyvohdjhg

協力お願いします

#1

投稿記事 by jvhdoyvohdjhg » 9年前

すべての順路を調べて最短と最長を調べているんですが、最長をどーやって表示させたらいいかわかりません。
端末で始点と終点を入力します。a点~e点まであり、a点は0、b点は1、・・・c点は4と考えて入力します。
また、つながっていない点同士のデータの値は1000にしてfor文でまわしています。
longP[5]の初期値も書いているのであってるのかよくわかりません。

コード:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<limits.h>

/*データ(隣接行列)*/
int d[5][5] = {
   /* a, b, c, d, e */
     1000, 8, 1000, 1000, 4,       /*a*/
     8, 1000, 5, 6, 1000,         /*b*/
     1000, 5, 1000, 3, 2,         /*c*/
     1000, 6, 3, 1000, 4,         /*d*/
     4, 1000, 2, 4, 1000,         /*e*/
};

void BF(int start, int goal){
    int shortL = 1000, longL = 0;
    int shortP[5]={-1,-1,-1,-1,-1}, longP[5]={-1,-1,-1,-1,-1};
    int i, j, k;
    int tmp;
    
    //2節点の場合
    tmp = d[start][goal];
    if(tmp < 1000){
        if(shortL > tmp){
            shortL = tmp;
            shortP[0] = start;
            shortP[1] = goal;
        }
        if(longL < tmp){
            longL = tmp;
            longP[0] = start;
            longP[1] = goal;
        }
    } 
    
    //3節点の場合
    for(i=0; i<5; i++){
        tmp = d[start][i] + d[i][goal];
        if(tmp < 1000){
            if(shortL > tmp){
                shortL = tmp;
                shortP[0] = start;
                shortP[1] = i;
                shortP[2] = goal;
            }
            if(longL < tmp){
                longL = tmp;
                longP[0] = start;
                longP[1] = i;
                longP[2] = goal;
            }
        }
    }
    
    //4節点の場合
    for(i=0; i<5; i++){
        for(j=0; j<5; j++){
            tmp = d[start][i] + d[i][j] + d[j][goal];
            if(tmp < 1000){
                if(shortL > tmp){
                    shortL = tmp;
                    shortP[0] = start;
                    shortP[1] = i;
                    shortP[2] = j;
                    shortP[3] = goal;
                    }
                    if(longL < tmp){
                    longL = tmp;
                    longP[0] = start;
                    longP[1] = i;
                    longP[2] = j;
                    longP[3] = goal;
                }
            }
        }  
    }
    
    //5節点の場合
    for(i=0; i<5; i++){
        for(j=0; j<5; j++){
            for(k=0; k<5; k++){
                tmp = d[start][i] + d[i][j] + d[j][k] + d[k][goal];
                if(tmp < 1000){
                    if(shortL > tmp){
                        shortL = tmp;
                        shortP[0] = start;
                        shortP[1] = i;
                        shortP[2] = j;
                        shortP[3] = k;
                        shortP[4] = goal;
                        }
                        if(longL < tmp){
                        longP[0] = start;
                        longP[1] = i;
                        longP[2] = j;
                        longP[3] = k;
                        longP[4] = goal;
                    }
                }
            }  
        }
    }
    
    if(start == goal){
        printf("最短経路");
        printf("%c->%c\n", start+97, goal+97);
        printf("最短経路長0\n");
    }else{
        printf("最短経路");
        printf("%c",shortP[0]+97);
        for(i=1; shortP[i] != -1; i++){
            printf("->%c",shortP[i]+97);
        }
        printf("\n最短経路長");
        printf("%d\n", shortL);
        
    }  

}
    
int main(){
    int start;
    int goal;
    
    while(1){
        printf("始点:");
        scanf("%d", &start);
        printf("終点:");
        scanf("%d", &goal);
        BF(start, goal);
    }
    
    return 0;
}
 

dfghjk

Re: 協力お願いします

#2

投稿記事 by dfghjk » 9年前

質問文の訂正 c点を4としていますが、正しくはe点が4でした

初級者
記事: 200
登録日時: 13年前

Re: 協力お願いします

#3

投稿記事 by 初級者 » 9年前

最短経路と同じように出力すればいいだけのような
気がします。ロジックが正しければ。

kyj

Re: 協力お願いします

#4

投稿記事 by kyj » 9年前

そーなんですけど上手くできません
やってみてもらえませんか?

初級者
記事: 200
登録日時: 13年前

Re: 協力お願いします

#5

投稿記事 by 初級者 » 9年前

いくつのお名前をお持ちなんでしょうか。

まあ、それはさておき、
うまくいかない
というからには、なにがしかのコードを
書かれたのですよね。

それを貼ってみよう、という
お気持ちはありますか?

アバター
ookami
記事: 214
登録日時: 13年前
住所: 東京都

Re: 協力お願いします

#6

投稿記事 by ookami » 9年前

たぶんですが、上で示されたコードでlongPやlongL等で最長を求めてようとしているのかなと。
その前に「最長」というのがよく分からないのは私だけでしょうか??
クリティカルパスを求めるときのように、それぞれのパスが一方通行なら最長が決まる気がしますが...

アバター
softya(ソフト屋)
副管理人
記事: 11677
登録日時: 13年前
住所: 東海地方
連絡を取る:

Re: 協力お願いします

#7

投稿記事 by softya(ソフト屋) » 9年前

当掲示板では名前の統一といい加減な(ふざけた名前)の利用禁止をルールとさせて頂いております。
よろしくお願いします。
フォーラムルール → http://dixq.net/board/board.html
課題の丸投げも禁止事項です。
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。

閉鎖

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