過去ログ
No．１１０４ ダイクストラ法を使った最短経路
[戻る] [ホームページ]No.1566 |
ダイクストラ法を使った最短経路 投稿者---deer(2004/04/11 07:53:08) |
||
ダイクストラ法を用いた最短経路の求め方を教えてください。 データは、2種類あります。 EUROPE.NAMES 8 amsterdam belgrade berlin bern brussels budapest copenhagen genoa hamburg EUROPE.DISTANCES 0 3 558 0 4 164 0 8 338 こういった感じです。 |
|||
| No.1569 |
Re:ダイクストラ法を使った最短経路 投稿者---とおりすがり(2004/04/11 17:44:04) |
||
丸投げは嫌われます… |
|||
| No.1570 |
Re:ダイクストラ法を使った最短経路 投稿者---たか(2004/04/11 17:53:54) |
||
有向か無向か、それから隣接行列か隣接リストですべての辺を入力する データを示して下さい。次に、以下のアルゴリズムがダイクストラの アルゴリズムと呼ばれるものです(boostのドキュメントからのコピペ ですが)。これらを用いてご自分でできる範囲までプログラムを書いて もう一度投稿されれば、どなたかが続きを教えてくれるかもしれません。 DIJKSTRA(G, s, w)
for each vertex u in V
d[u] := infinity
p[u] := u
color[u] := WHITE
end for
color[s] := GRAY
d[s] := 0
INSERT(Q, s)
while (Q != Ø)
u := EXTRACT-MIN(Q)
S := S U { u }
for each vertex v in Adj[u]
if (w(u,v) + d[u] < d[v])
d[v] := w(u,v) + d[u]
p[v] := u
if (color[v] = WHITE)
color[v] := GRAY
INSERT(Q, v)
else if (color[v] = GRAY)
DECREASE-KEY(Q, v)
else
...
end for
color[u] := BLACK
end while
return (d, p)
|
|||
| No.1571 |
Re:ダイクストラ法を使った最短経路 投稿者---deer(2004/04/12 01:49:09) |
||
作ってみました。 自分の頭の中で、整理できずに作ったので、めちゃくちゃかもしれません。 ご教授、お願いします。
#include<studio.h>
#include<stdlib.h>
#include<limits.h>
#define MaxN 50
#define TRUE 1
#define FALSE 0
int adj[MaxN][MaxN];
int visited[MaxN];
int prev[MaxN];
int distance[MaxN];
void Dijkstra(int start){
int next;
distance[start] = 0;
do{
int i;
int min = INT_MAX;
next = -1;
visited[start] = TRUE;
for(i = 0; i < MaxN; i++){
if(visited[i]) continue;
if(adj[start][i]){
int d = distance[start] + adj[start][i];
if(d < distance[i]){
distance[i] = d;
prev[i] = start;
}
}
if(min > distance[i]){
min = distance[i];
next = i;
}
}
}while((start = next) != -1);
}
int main(){
int i;
int n, visiti, visitj, disij;
char startcity, endingcity, totaldis;
char cname[i];
FILE *name, *dis;
name = fopen("EUROPE.NAMES", "r");
fscanf(name, "%d", &n);
for(i = 1; i <= n; i++){
fscanf(name, "%s", &cname);
}
dis = fopen("EUROPE.DISTANCES", "r");
while(fscanf(dis, "%d %d %d", &visiti, &visitj, &disij) != EOF){
adj[visiti][visitj] = adj[visitj][visiti] = disij;
}
if(name == NULL && dis == NULL){
printf("Graph Data couldn't open!!\n");
exit(1);
}
printf("OK, Graph Data Loaded\n");
for(;;){
printf("Start City (Q to quit) : ");
scanf("%s", &startcity);
if(startcity == 'Q' || startcity == 'q'){
exit(1);
}
printf("Ending City : ");
scanf("%s", &endingcity);
Dijkstra(0);
printf("Shortest Route : %s", &startcity);
for(i = 0; i < MaxN; i++){
printf(" / %s", cname[i]);
}
printf("Total Distance : %d", distance[i]);
}
}
|
|||
| No.1572 |
Re:ダイクストラ法を使った最短経路 投稿者---たか(2004/04/12 15:47:31) |
||
>作ってみました。 >自分の頭の中で、整理できずに作ったので、めちゃくちゃかもしれません。 >ご教授、お願いします。 で、このプログラムの実行結果は思う通りに行きましたか？完全な入力 データが示されていないので、こちらでは検証できません。 もちろんこちらで本に載っているような代表的なプログラムを示す事は 簡単ですが、それではＢＢＳの意味がありませんから。 |
|||
| No.1573 |
Re:ダイクストラ法を使った最短経路 投稿者---たか(2004/04/12 15:48:23) |
||
>で、このプログラムの実行結果は思う通りに行きましたか？完全な入力 >データが示されていないので、こちらでは検証できません。 具体的にはEUROPE.NAMESとEUROPE.DISDANCESのファイルの中身も見せて 下さい。 |
|||
| No.1574 |
Re:ダイクストラ法を使った最短経路 投稿者---deer(2004/04/12 22:36:01) |
||
>>で、このプログラムの実行結果は思う通りに行きましたか？完全な入力 >>データが示されていないので、こちらでは検証できません。 > >具体的にはEUROPE.NAMESとEUROPE.DISDANCESのファイルの中身も見せて >下さい。 一番初めの投稿で、書いておいたと思うのですが、足りないでしょうか？ 実際はもっとデータがあるのですが･・・ |
|||
| No.1575 |
Re:ダイクストラ法を使った最短経路 投稿者---たか(2004/04/13 09:18:06) |
||
>一番初めの投稿で、書いておいたと思うのですが、足りないでしょうか？ >実際はもっとデータがあるのですが･・・ そうですね、そうしたら行けないパスは表示しない事にしましょう。 INT_MAXを使うと計算途中でオーバーフローが起きて一挙に負の数になる 可能性があるので、使いませんでした。 #include <stdio.h>
#include <stdlib.h>
#include <string>
#define MaxN 50
#define TRUE 1
#define FALSE 0
#define MaxC 128
#define MaxD 999999
int adj[MaxN][MaxN];
int visited[MaxN];
int prev[MaxN + 1];
int distance[MaxN];
void Dijkstra(int start, int n)
{
int i, j, k, dmin;
for (i = 0; i < n; i++) {
visited[i] = FALSE;
distance[i] = MaxD;
prev[i] = -1; /* prevは都市名が0で始めるため-1をエンドマークとする */
}
prev[i] = -1;
distance[start] = 0;
prev[start] = -1;
for (j = 0; j < n; j++) {
dmin = MaxD;
for (k = 0; k < n; k++)
if (visited[k] == FALSE && distance[k] < dmin) {
i = k; dmin = distance[k];
}
visited[i] = TRUE;
if (dmin == MaxD); /* 始点へ至るpathがない */
else
for (k = 0; k < n; k++)
if (distance[i] + adj[i][k] < distance[k]) {
distance[k] = distance[i] + adj[i][k];
prev[k + 1] = i;
}
}
}
int main(void)
{
int i, j;
int n, visiti, visitj, disij;
int startcity;
char cname[MaxN][MaxC], buf[MaxC];
FILE *name, *dis;
name = fopen("EUROPE.NAMES", "r");
dis = fopen("EUROPE.DISTANCES", "r");
if (name == NULL || dis == NULL) {
printf("Graph Data couldn't open!!\n");
exit(1);
}
fgets(buf, MaxC, name);
sscanf(buf, "%d", &n);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
adj[i][j] = MaxD;
for(i = 0; i < n; i++) {
fgets(cname[i], MaxC, name);
cname[i][strlen(cname[i]) - 1] = '\0';
}
while (fgets(buf, MaxC, dis)) {
sscanf(buf, "%d %d %d", &visiti, &visitj, &disij);
adj[visiti][visitj] = adj[visitj][visiti] = disij; /* 有向グラフだが反対方向の重みは同じ */
}
fclose(dis); fclose(name);
printf("read names count is %d:\n", n);
for (i = 0; i < n; i++)
printf("%d : %s\n", i, cname[i]);
printf("OK, Graph Data Loaded\n");
for (;;) {
printf("Start City (-1 to quit) : ");
scanf("%d", &startcity);
if (startcity == -1)
exit(1);
Dijkstra(startcity, n);
printf("Start = %s\n", cname[startcity]);
for (i = 0; i < n; i++) {
if (distance[i] == MaxD) continue; /* 経路なし */
printf("Distance = %d, Shortest Route : %s ", distance[i], cname[i]);
j = i;
while (prev[j + 1] >= 0) {
printf(" <- %s", cname[prev[j + 1]]);
j = prev[j + 1];
}
printf("\n");
}
}
}
|
|||
| No.1576 |
Re:ダイクストラ法を使った最短経路 投稿者---たか(2004/04/13 09:22:55) |
||
deerさんに頂いたソースですが、いろいろいじくり回してみましたが どうも動きませんでしたのでごっそり変えてしまいました。 ダイクストラのアルゴリズムはいく種類か変形がありますが、基本とな る動きは同じです。 |
|||
| No.1577 |
Re:ダイクストラ法を使った最短経路 投稿者---deer(2004/04/14 00:25:28) |
||
>deerさんに頂いたソースですが、いろいろいじくり回してみましたが >どうも動きませんでしたのでごっそり変えてしまいました。 みたいですね。 お手数お掛けして、すみません。 >ダイクストラのアルゴリズムはいく種類か変形がありますが、基本とな >る動きは同じです。 なるほど。 たかさんに作っていただいたものは、わかりやすい気がします。 ところで、私の始めに作ったプログラムに、Ending Cityってあったと思うんです。 始めに、標準入力から、Start City と Ending City を入力して、その間の最短距離を求めたいのです。 いろいろいじくっていたら、セグメント例外が出てしまいました･･･。 あと、リストにない都市を入力した場合には、エラーメッセージを出す必要がありますが、それは、文字列比較を使って処理すればいいのでしょうか。 一応、下にいじくった後のものを載せておきます。 基本的には、たかさんのとあまり変わっていないようですが･･・ ※ユーザーインターフェースにいくぶん制約があるので、そこは、変えさせていただきました。すみません。 #include <stdio.h>
#include <stdlib.h>
/*#include <string>*/
#define MaxN 50
#define TRUE 1
#define FALSE 0
#define MaxC 128
#define MaxD 999999
int adj[MaxN][MaxN];
int visited[MaxN];
int prev[MaxN + 1];
int weight[MaxN];
void Dijkstra(int start, int n){
int i, j, k, dmin;
for(i = 0; i < n; i++){
visited[i] = FALSE;
weight[i] = MaxD;
prev[i] = -1; /* -1 = end mark */
}
prev[i] = -1;
weight[start] = 0;
prev[start] = -1;
for(j = 0; j < n; j++){
dmin = MaxD;
for (k = 0; k < n; k++){
if (visited[k] == FALSE && weight[k] < dmin) {
i = k;
dmin = weight[k];
}
}
visited[i] = TRUE;
if(dmin == MaxD); /* no path (to startcity) */
else
for(k = 0; k < n; k++){
if(weight[i] + adj[i][k] < weight[k]){
weight[k] = weight[i] + adj[i][k];
prev[k + 1] = i;
}
}
}
}
int main(void){
int i, j;
int n, visiti, visitj, distance;
int startcity, endingcity;
char cname[MaxN][MaxC], buf[MaxC];
FILE *name, *dis;
name = fopen("EUROPE.NAMES", "r");
dis = fopen("EUROPE.DISTANCES", "r");
if (name == NULL || dis == NULL) {
printf("Graph Data couldn't open!!\n");
exit(1);
}
fgets(buf, MaxC, name);
sscanf(buf, "%d", &n);
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
adj[i][j] = MaxD;
}
}
for(i = 0; i < n; i++){
fgets(cname[i], MaxC, name);
cname[i][strlen(cname[i]) - 1] = '\0';
}
while(fgets(buf, MaxC, dis)){
sscanf(buf, "%d %d %d", &visiti, &visitj, &distance);
adj[visiti][visitj] = adj[visitj][visiti] = distance;
}
fclose(dis);
fclose(name);
printf("read names count is %d:\n", n);
for (i = 0; i < n; i++){
printf("%d : %s\n", i, cname[i]);
}
printf("OK, Graph Data Loaded\n");
for(;;){
printf("Start City (Q to quit) : ");
scanf("%s", &startcity);
if(startcity == 'Q' || startcity == 'q'){
exit(1);
}
printf("Ending City : ");
scanf("%s", &endingcity);
/* if・・・・ここで文字列比較をやろうかと・・・*/
Dijkstra(startcity, n);
for(i = 0; i < n; i++){
if(weight[i] == MaxD){/* no path */
printf("There are no path!!\n");
continue;
}
printf("Shortest Route : %s ", cname[i]);
j = i;
while(prev[j + 1] >= 0){
printf(" / %s", cname[prev[j + 1]]);
j = prev[j + 1];
}
printf("\n");
printf("Total Distance : %d", weight[i]);
}
}
}
|
|||
| No.1578 |
Re:ダイクストラ法を使った最短経路 投稿者---たか(2004/04/14 11:33:20) |
||
>ところで、私の始めに作ったプログラムに、Ending Cityってあったと思うんです。 >始めに、標準入力から、Start City と Ending City を入力して、その間の最短距離を求めたいのです。 >いろいろいじくっていたら、セグメント例外が出てしまいました･･･。 > >あと、リストにない都市を入力した場合には、エラーメッセージを出す必要がありますが、それは、文字列比較を使って処理すればいいのでしょうか。 StartCityとEndingCityは数字で入力するのでしょうか。それとも文字列 で入力するのでしょうか。最初にいただいたプログラムではcharの配列 ではなくchar型の変数に文字列を読み込もうとしていたので、これなら 数字で入力した方がいいと思い、そのように変えました。 現在はStartCityとEndingCityはint型に変えてあります。ここに"%s"変換 で文字列を読み込むと、当然長い文字列はint型の幅を超えて代入される ので、振る舞いは未定義です。 リストにない都市を入力してエラーが出るようにするのは簡単です。 |
|||
| No.1579 |
Re:ダイクストラ法を使った最短経路 投稿者---たか(2004/04/14 11:34:50) |
||
それから<string.h>をコメントアウトしてありますが、strlen()関数を 使用しているので、コメントアウトしないで下さい。 |
|||
| No.1580 |
Re:ダイクストラ法を使った最短経路 投稿者---たか(2004/04/14 12:04:15) |
||
あちこちいじくっていたら、かなり汚くなってきました(^_^;)。 都市名を文字列で入れるプログラムは、宿題とします。都市名は0からで なく1から始まるように都合上変えています。 #include <stdio.h>
#include <stdlib.h>
#include <string>
#define MaxN 50
#define TRUE 1
#define FALSE 0
#define MaxC 128
#define MaxD 999999
int adj[MaxN][MaxN];
int visited[MaxN];
int prev[MaxN + 1];
int weight[MaxN];
void Dijkstra(int start, int n)
{
int i, j, k, dmin;
for (i = 0; i < n; i++) {
visited[i] = FALSE;
weight[i] = MaxD;
prev[i] = -1; /* prevは都市名が0で始めるため-1をエンドマークとする */
}
prev[i] = -1;
weight[start] = 0;
prev[start] = -1;
for (j = 0; j < n; j++) {
dmin = MaxD;
for (k = 0; k < n; k++)
if (visited[k] == FALSE && weight[k] < dmin) {
i = k; dmin = weight[k];
}
visited[i] = TRUE;
if (dmin == MaxD); /* 始点へ至るpathがない */
else
for (k = 0; k < n; k++)
if (weight[i] + adj[i][k] < weight[k]) {
weight[k] = weight[i] + adj[i][k];
prev[k + 1] = i;
}
}
}
int main(void)
{
int i, j;
int n, visiti, visitj, distance;
int startcity, endingcity;
char cname[MaxN][MaxC], buf[MaxC];
FILE *name, *dis;
name = fopen("EUROPE.NAMES", "r");
dis = fopen("EUROPE.DISTANCES", "r");
if (name == NULL || dis == NULL) {
printf("Graph Data couldn't open!!\n");
exit(1);
}
fgets(buf, MaxC, name);
sscanf(buf, "%d", &n);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
adj[i][j] = MaxD;
for(i = 0; i < n; i++) {
fgets(cname[i], MaxC, name);
cname[i][strlen(cname[i]) - 1] = '\0';
}
while (fgets(buf, MaxC, dis)) {
sscanf(buf, "%d %d %d", &visiti, &visitj, &distance);
adj[visiti][visitj] = adj[visitj][visiti] = distance; /* 有向グラフだが反対方向の重みは同じ */
}
fclose(dis);
fclose(name);
printf("read names count is %d:\n", n);
for (i = 0; i < n; i++)
printf("%d : %s\n", i + 1, cname[i]);
printf("OK, Graph Data Loaded\n");
while (1) {
while (1) {
printf("Start City (Q to quit) : ");
fgets(buf, MaxC, stdin);
if (*buf == '\n') continue;
else if (*buf == 'Q' || *buf == 'q') exit(0);
sscanf(buf, "%d", &startcity);
if (0 < startcity && startcity <= n)
break;
printf("Enter city number between 1 - %d.\n", n);
}
while (1) {
printf("Ending City : ");
fgets(buf, MaxC, stdin);
if (*buf == '\n') continue;
sscanf(buf, "%d", &endingcity);
if (0 < endingcity && endingcity <= n)
break;
printf("Enter city number between 1 - %d.\n", n);
}
Dijkstra(startcity - 1, n);
for (i = 0; i < n; i++) {
if (i == endingcity - 1) {
if (weight[i] == MaxD) { /* 経路なし */
printf("No route from %s to %s.\n", cname[startcity - 1], cname[i]);
break;
}
printf("Shortest Route : %s", cname[i]);
j = i;
while (prev[j + 1] >= 0) {
printf(" / %s", cname[prev[j + 1]]);
j = prev[j + 1];
}
printf("\n");
printf("Total distance : %d\n", weight[i]);
}
}
}
}
|
|||
| No.1581 |
Re:ダイクストラ法を使った最短経路 投稿者---deer(2004/04/14 22:35:09) |
||
仕様では、都市名は文字列で入力することになってました。 名前で入力する部分、考えてみます。 |
|||
| No.1582 |
Re:ダイクストラ法を使った最短経路 投稿者---たか(2004/04/14 23:15:56) |
||
>仕様では、都市名は文字列で入力することになってました。 >名前で入力する部分、考えてみます。 では、一つアドバイスを。元にいただいたプログラムは文字列を"%s"変換 で受け取るようになっていましたが、これでは"bern brussels"のように 途中にホワイトスペース文字を挟む都市名がちょん切れてしまいます。 そのためfgets()を使うようにし、またfgets()では文字列の終端に'\n'が 入ってしまうため、それを除去するのにstrlen()を使ったという次第です。 目標は都市名→0〜nのint型に変換するルーチンを作成すればいいと思い ます。cname[]とstrcmp()を組み合わせればいいはずです。 |
|||
| No.1583 |
Re:ダイクストラ法を使った最短経路 投稿者---deer(2004/04/15 13:22:28) |
||
>では、一つアドバイスを。元にいただいたプログラムは文字列を"%s"変換 >で受け取るようになっていましたが、これでは"bern brussels"のように >途中にホワイトスペース文字を挟む都市名がちょん切れてしまいます。 > >そのためfgets()を使うようにし、またfgets()では文字列の終端に'\n'が >入ってしまうため、それを除去するのにstrlen()を使ったという次第です。 この件については、今回のケースの場合、そういった名前の都市がないので、特に考えることはないかなと思いました。でも、”汎用性”のことを考えると、そうすべきなのですね。きっと。 >目標は都市名→0〜nのint型に変換するルーチンを作成すればいいと思い >ます。cname[]とstrcmp()を組み合わせればいいはずです。 作ってみた･･･つもりなのですが、やっぱりおかしいです。 リストにない都市名を入れても、エラーメッセージはでないですし、 もちろん、結果も出てきません。 どこがおかしいのか、ご指摘、お願いします。 #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MaxN 50
#define TRUE 1
#define FALSE 0
#define MaxC 128
#define MaxD 999999
int adj[MaxN][MaxN];
int visited[MaxN];
int prev[MaxN + 1];
int weight[MaxN];
void Dijkstra(int start, int n){
int i, j, k, dmin;
for(i = 0; i < n; i++){
visited[i] = FALSE;
weight[i] = MaxD;
prev[i] = -1; /* -1 = end mark */
}
prev[i] = -1;
weight[start] = 0;
prev[start] = -1;
for(j = 0; j < n; j++){
dmin = MaxD;
for (k = 0; k < n; k++){
if (visited[k] == FALSE && weight[k] < dmin) {
i = k;
dmin = weight[k];
}
}
visited[i] = TRUE;
if(dmin == MaxD); /* no path (to startcity) */
if(dmin == MaxD); /* no path (to startcity) */
else
for(k = 0; k < n; k++){
if(weight[i] + adj[i][k] < weight[k]){
weight[k] = weight[i] + adj[i][k];
prev[k + 1] = i;
}
}
}
}
int main(void){
int i, j;
int n, visiti, visitj, distance;
int ret1, ret2;
char startcity, endingcity;
char cname[MaxN][MaxC], buf[MaxC];
FILE *name, *dis;
name = fopen("EUROPE.NAMES", "r");
dis = fopen("EUROPE.DISTANCES", "r");
if (name == NULL || dis == NULL) {
printf("Graph Data couldn't open!!\n");
exit(1);
}
fgets(buf, MaxC, name);
sscanf(buf, "%d", &n);
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
adj[i][j] = MaxD;
}
}
for(i = 0; i < n; i++){
fgets(cname[i], MaxC, name);
cname[i][strlen(cname[i]) - 1] = '\0';
}
while(fgets(buf, MaxC, dis)){
sscanf(buf, "%d %d %d", &visiti, &visitj, &distance);
adj[visiti][visitj] = adj[visitj][visiti] = distance;
}
fclose(dis);
fclose(name);
printf("read names count is %d:\n", n);
for (i = 0; i < n; i++){
printf("%d : %s\n", i+1, cname[i]);
}
printf("OK, Graph Data Loaded\n");
while(1){
while(1){
printf("\nStart City (Q to quit) : ");
scanf("%s", &startcity);
if(startcity == 'Q' || startcity == 'q'){
exit(0);
}
printf("Ending City : ");
scanf("%s", &endingcity);
ret1 = strcmp(&startcity, cname[i]);
ret2 = strcmp(&endingcity, cname[i]);
if(ret1 > 0 || ret2 < 0){
printf("There is no city!!\n");
break;
}
}
Dijkstra(startcity - 1, n);
for(i = 0; i < n; i++){
if(i == endingcity - 1){
if(weight[i] == MaxD){/* no path */
printf("No route from %s to %s.\n",
cname[startcity - 1], cname[i]);
break;
}
printf("Shortest Route : %s ", cname[i]);
j = i;
while(prev[j + 1] >= 0){
printf(" / %s", cname[prev[j + 1]]);
j = prev[j + 1];
}
printf("\n");
printf("Total Distance : %d", weight[i]);
}
}
}
}
|
|||
| No.1584 |
Re:ダイクストラ法を使った最短経路 投稿者---たか(2004/04/15 15:30:27) |
||
>この件については、今回のケースの場合、そういった名前の都市がないの >で、特に考えることはないかなと思いました。でも、”汎用性”のことを >考えると、そうすべきなのですね。きっと。 あー、という事は"bern brussels"は間違いなのですね。確かにこういう 都市名は実在しません。しかし都市名数が8とあるのと、行数が8で一致 するので一行ずらすのも何かと思い、そのままにしておきました。正しく プログラムが動くのを確認するために、ファイル'EUROPE.NAMES'を直して おいて下さい。具体的には"bern"と"brussels"の間に改行を入れ、行数を 9として下さい。 >作ってみた･･･つもりなのですが、やっぱりおかしいです。 >リストにない都市名を入れても、エラーメッセージはでないですし、 >もちろん、結果も出てきません。 >どこがおかしいのか、ご指摘、お願いします。 動かなかった理由は、startcityとendingcityがchar型で定義されていた せいです。一度char型の配列に読み込み、後で整数に変換する必要があり ます。これはCには文字列という概念がないために起こります。 |
|||
| No.1585 |
Re:ダイクストラ法を使った最短経路 投稿者---たか(2004/04/15 15:32:05) |
||
入力されたデータにない都市名を入れると警告を発して('\a')再入力 を促すようにしておきましたのでお好みによって改造して下さい。 #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MaxN 50
#define TRUE 1
#define FALSE 0
#define MaxC 128
#define MaxD 999999
int adj[MaxN][MaxN];
int visited[MaxN];
int prev[MaxN + 1];
int weight[MaxN];
void Dijkstra(int start, int n){
int i, j, k, dmin;
for(i = 0; i < n; i++){
visited[i] = FALSE;
weight[i] = MaxD;
prev[i] = -1; /* -1 = end mark */
}
prev[i] = -1;
weight[start] = 0;
prev[start] = -1;
for(j = 0; j < n; j++){
dmin = MaxD;
for (k = 0; k < n; k++){
if (visited[k] == FALSE && weight[k] < dmin) {
i = k;
dmin = weight[k];
}
}
visited[i] = TRUE;
if(dmin == MaxD); /* no path (to startcity) */
else
for(k = 0; k < n; k++){
if(weight[i] + adj[i][k] < weight[k]){
weight[k] = weight[i] + adj[i][k];
prev[k + 1] = i;
}
}
}
}
int checkcity(const char *buf, const char cityname[][MaxC], int n)
{
int i;
for (i = 0; i < n; i++)
if (!strcmp(buf, cityname[i])) return i + 1; /* linear search */
return 0;
}
int main(void){
int i, j;
int n, visiti, visitj, distance;
int startcity, endingcity;
char startcitybuf[MaxC], endingcitybuf[MaxC]; /* char型の配列で定義する必要がある */
char cname[MaxN][MaxC], buf[MaxC];
FILE *name, *dis;
name = fopen("EUROPE.NAMES", "r");
dis = fopen("EUROPE.DISTANCES", "r");
if (name == NULL || dis == NULL) {
printf("Graph Data couldn't open!!\n");
exit(1);
}
fgets(buf, MaxC, name);
sscanf(buf, "%d", &n);
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
adj[i][j] = MaxD;
}
}
for(i = 0; i < n; i++){
fgets(cname[i], MaxC, name);
cname[i][strlen(cname[i]) - 1] = '\0';
}
while(fgets(buf, MaxC, dis)){
sscanf(buf, "%d %d %d", &visiti, &visitj, &distance);
adj[visiti][visitj] = adj[visitj][visiti] = distance;
}
fclose(dis);
fclose(name);
printf("read names count is %d:\n", n);
for (i = 0; i < n; i++)
puts(cname[i]);
printf("OK, Graph Data Loaded\n");
while(1) {
while(1) {
printf("Start City (Q to quit) : ");
fgets(startcitybuf, MaxC, stdin); /* "%s"では途中にホワイトスペース文字があると正しく読み取れない */
startcitybuf[strlen(startcitybuf) - 1] = '\0';
if(*startcitybuf == 'Q' || *startcitybuf == 'q'){
exit(0);
}
if ((startcity = checkcity(startcitybuf, cname, n)) != 0)
break;
puts("\aEnter collect city name");
}
while (1) {
printf("Ending City : ");
fgets(endingcitybuf, MaxC, stdin);
endingcitybuf[strlen(endingcitybuf) - 1] = '\0';
if ((endingcity = checkcity(endingcitybuf, cname, n)) != 0)
break;
puts("\aEnter collect city name");
}
startcity--; endingcity--;
Dijkstra(startcity, n);
for(i = 0; i < n; i++){
if(i == endingcity){
if(weight[i] == MaxD){/* no path */
printf("No route from %s to %s.\n", cname[startcity], cname[i]);
break;
}
printf("Shortest Route : %s ", cname[i]);
j = i;
while(prev[j + 1] >= 0){
printf(" / %s", cname[prev[j + 1]]);
j = prev[j + 1];
}
printf("\n");
printf("Total Distance : %d\n", weight[i]);
}
}
}
}
|
|||
| No.1586 |
Re:ダイクストラ法を使った最短経路 投稿者---たか(2004/04/15 23:57:47) |
||
えーと、次の部分のfor()ループは無駄ですね。取り去るといいですね。 時間が遅いのでまた明日にでも。 for(i = 0; i < n; i++){
if(i == endingcity){
if(weight[i] == MaxD){/* no path */
printf("No route from %s to %s.\n", cname[startcity], cname[i]);
break;
}
printf("Shortest Route : %s ", cname[i]);
j = i;
while(prev[j + 1] >= 0){
printf(" / %s", cname[prev[j + 1]]);
j = prev[j + 1];
}
printf("\n");
printf("Total Distance : %d\n", weight[i]);
}
}
}
}
|
|||
| No.1587 |
Re:ダイクストラ法を使った最短経路 投稿者---deer(2004/04/16 03:09:52) |
||
大変なことをチェックし忘れていたようです。 今見てびっくりしてしまいました･･笑 仕様によると、 最低でも以下のとおりの関数に分けなければならないようでした。 ・Build_graph ・Find_start_dest_numbers ・Initialize_3_arrays ・Do_Dijkstra_search ・report_answer あと、グラフをストアするときに、３つの可能性があるとして、処理しなさいとありました。 １）もしエッジがあるなら、実際のweight（重み）を ２）マトリックスの対角線上は、０に。 ３）エッジがないときは、MAXINT（無限大）とする。 自分である程度いじってから、また投稿します。 |
|||
| No.1588 |
Re:ダイクストラ法を使った最短経路 投稿者---deer(2004/04/16 08:42:09) |
||
>仕様によると、 >最低でも以下のとおりの関数に分けなければならないようでした。 >・Build_graph >・Find_start_dest_numbers >・Initialize_3_arrays >・Do_Dijkstra_search >・report_answer 一応、上のものを分けてみたのですが、Find_start_dest_numbersがちょっとわかりませんでした。。。 おかげさまで、以下のとおり、一応プログラム的にはできたかな？という感じですが、 １つ問題点が･･･。 というのも、Shortest Routeの表示をする場合に、 endingcity → startcity の順になっていますが、 startcity → endingcity の順にしなければなりません。 この場合、どうしたらいいのでしょうか。 #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MaxN 50
#define TRUE 1
#define FALSE 0
#define MaxC 128
#define MaxD 999999 /* = MaxInt */
int adj[MaxN][MaxN];
int visited[MaxN];
int prev[MaxN + 1];
int weight[MaxN];
char cname[MaxN][MaxC];
char buf[MaxC];
FILE *name, *dis;
void Do_Dijkstra_search(int start, int n){
int i, j, k, dmin;
for(i = 0; i < n; i++){
visited[i] = FALSE;
weight[i] = MaxD;
prev[i] = -1; /* -1 = end mark */
}
/* Initialize_3_arrays */
prev[i] = -1;
weight[start] = 0;
prev[start] = -1;
for(j = 0; j < n; j++){
dmin = MaxD;
for (k = 0; k < n; k++){
if (visited[k] == FALSE && weight[k] < dmin) {
i = k;
dmin = weight[k];
}
}
visited[i] = TRUE;
if(dmin == MaxD); /* no path (to startcity) */
else
for(k = 0; k < n; k++){
if(weight[i] + adj[i][k] < weight[k]){
weight[k] = weight[i] + adj[i][k];
prev[k + 1] = i;
}
}
}
}
int checkcity(const char *buf, int n){
int i;
for(i = 0; i < n; i++){
if(!strcmp(buf, cname[i])){
return i + 1;
}
}
return 0;
}
int Report_answer(int n){
int i, j;
int startcity, endingcity, city = -1;
char startcitybuf[MaxC], endingcitybuf[MaxC];
printf("OK, Graph Data Loaded\n");
while(1){
while(1){
printf("\nStart City (Q to quit) : ");
scanf("%s", &startcitybuf);
if(*startcitybuf == 'Q' || *startcitybuf == 'q'){
exit(0);
}
startcity = checkcity(startcitybuf, n);
if(startcity != 0)
break;
printf("There is no %s on the data.\n", &startcitybuf);
break;
}
while(1){
printf("Ending City : ");
scanf("%s", &endingcitybuf);
endingcity = checkcity(endingcitybuf, n);
if(endingcity != 0 || (startcity = 0 && endingcity != 0))
break;
printf("There is no %s on the data.\n", &endingcitybuf);
break;
}
startcity--;
endingcity--;
Do_Dijkstra_search(startcity, n);
for(i = 0; i < n; i++){
if(i == endingcity){
if(weight[i] == MaxD){/* no path */
break;
}
printf("Shortest Route : %s ", cname[i]);
j = i;
while(prev[j + 1] >= 0){
printf(" / %s", cname[prev[j + 1]]);
j = prev[j + 1];
}
printf("\n");
printf("Total Distance : %d\n", weight[i]);
}
}
}
}
int Build_graph(int n){
int i, j;
int visiti, visitj, distance;
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
adj[i][j] = MaxD;
}
}
for(i = 0; i < n; i++){
fgets(cname[i], MaxC, name);
cname[i][strlen(cname[i]) - 1] = '\0';
}
while(fgets(buf, MaxC, dis)){
sscanf(buf, "%d %d %d", &visiti, &visitj, &distance);
adj[visiti][visitj] = adj[visitj][visiti] = distance;
}
}
int main(int n){
name = fopen("EUROPE.NAMES", "r");
dis = fopen("EUROPE.DISTANCES", "r");
if (name == NULL || dis == NULL) {
printf("Graph Data couldn't open!!\n");
exit(1);
}
fgets(buf, MaxC, name);
sscanf(buf, "%d", &n);
Build_graph(n);
Report_answer(n);
fclose(dis);
fclose(name);
}
|
|||
| No.1589 |
Re:ダイクストラ法を使った最短経路 投稿者---たか(2004/04/16 15:47:08) |
||
あの・・・・ちょっと失礼しますが、投稿されているプログラムはコンパ イルを試されていますか？たくさんコンパイルエラーが出ます。最低限 コンパイルは通るようにしてから投稿して下さい。もしコンパイルが通ら ないまま投稿される時は、「・・・・・のようなコンパイルエラーが出ま す。なぜでしょうか」と明記して下さい。お願いします。 これでは本当に私の書いたプログラムを理解して下さっているのか、心配 になります。 できればコンパイル警告もできるだけ出ないようにして下さい。学校の 課題か何かだと思いますが、コンパイル警告が多く出るまま提出されると 先生の心証を悪くします。 それからいろいろと細かい事を書いて済みませんが、そろそろグローバル 変数が多くなってきました。C言語はOOP言語ではないのでカプセル化は 困難ですが、構造体を作ってmain()で定義し、各変数へ構造体へのポイン タを渡すぐらいはやっておくべきかと思います。 startcityから初めてendingcityに至るように表示を逆順にするのはいろ いろと方法がありますが、ダイクストラのアルゴリズムの性質上初めか ら逆順に格納するのは困難なので、再帰によってちょっとしたおまじない をかけておきました。 |
|||
| No.1590 |
Re:ダイクストラ法を使った最短経路 投稿者---たか(2004/04/16 15:47:59) |
||
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MaxN 50
#define TRUE 1
#define FALSE 0
#define MaxC 128
#define MaxD 999999 /* = MaxInt */
int adj[MaxN][MaxN];
int visited[MaxN];
int prev[MaxN + 1];
int weight[MaxN];
char cname[MaxN][MaxC];
char buf[MaxC];
FILE *name, *dis;
void Do_Dijkstra_search(int start, int n);
int checkcity(const char *buf, int n);
int Report_answer(int n);
void print_routes(int end);
void Build_graph(int n);
int main(void){
int n;
name = fopen("EUROPE.NAMES", "r");
dis = fopen("EUROPE.DISTANCES", "r");
if (name == NULL || dis == NULL) {
printf("Graph Data couldn't open!!\n");
exit(1);
}
fgets(buf, MaxC, name);
sscanf(buf, "%d", &n);
Build_graph(n);
Report_answer(n);
fclose(dis);
fclose(name);
return 0;
}
void Do_Dijkstra_search(int start, int n){
int i, j, k, dmin;
for(i = 0; i < n; i++){
visited[i] = FALSE;
weight[i] = MaxD;
prev[i] = -1; /* -1 = end mark */
}
/* Initialize_3_arrays */
prev[i] = -1;
weight[start] = 0;
prev[start] = -1;
for(j = 0; j < n; j++){
dmin = MaxD;
for (k = 0; k < n; k++){
if (visited[k] == FALSE && weight[k] < dmin) {
i = k;
dmin = weight[k];
}
}
visited[i] = TRUE;
if(dmin == MaxD); /* no path (to startcity) */
else
for(k = 0; k < n; k++){
if(weight[i] + adj[i][k] < weight[k]){
weight[k] = weight[i] + adj[i][k];
prev[k + 1] = i;
}
}
}
}
int Report_answer(int n){
int i, j;
int startcity, endingcity;
char startcitybuf[MaxC], endingcitybuf[MaxC];
printf("OK, Graph Data Loaded\n");
while(1){
while(1){
printf("\nStart City (Q to quit) : ");
scanf("%s", &startcitybuf);
if(*startcitybuf == 'Q' || *startcitybuf == 'q'){
exit(0);
}
startcity = checkcity(startcitybuf, n);
if(startcity != 0)
break;
printf("There is no %s on the data.\n", &startcitybuf);
break;
}
while(1){
printf("Ending City : ");
scanf("%s", &endingcitybuf);
endingcity = checkcity(endingcitybuf, n);
if(endingcity != 0)
break;
printf("There is no %s on the data.\n", &endingcitybuf);
break;
}
startcity--;
endingcity--;
Do_Dijkstra_search(startcity, n);
if (weight[endingcity] == MaxD) /* no path */
printf("No route from %s to %s.\n", cname[startcity], cname[endingcity]);
else {
printf("Shortest Route : %s ", cname[startcity]);
print_routes(endingcity);
printf("\nTotal Distance : %d\n", weight[endingcity]);
}
}
}
int checkcity(const char *buf, int n){
int i;
for(i = 0; i < n; i++){
if(!strcmp(buf, cname[i])){
return i + 1;
}
}
return 0;
}
void print_routes(int end)
{
if (prev[end + 1] >= 0) {
print_routes(prev[end + 1]);
printf(" / %s", cname[end]);
}
}
void Build_graph(int n){
int i, j;
int visiti, visitj, distance;
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
adj[i][j] = MaxD;
}
}
for(i = 0; i < n; i++){
fgets(cname[i], MaxC, name);
cname[i][strlen(cname[i]) - 1] = '\0';
}
while(fgets(buf, MaxC, dis)){
sscanf(buf, "%d %d %d", &visiti, &visitj, &distance);
adj[visiti][visitj] = adj[visitj][visiti] = distance;
}
}
|
|||
| No.1592 |
グローバル変数の意味 投稿者---たか(2004/04/16 15:54:07) |
||
ここを参照してください。 |
|||
| No.1593 |
Re:グローバル変数の意味 投稿者---たか(2004/04/16 15:58:28) |
||
あと、構造体のポインタを渡す他に各関数で必要とする変数のみ値渡し または参照渡し(Cではポインタ渡し)をして、各関数でどの引数を必要 としているのか明確化する方法もあります。 関数の引数が長くなりますが、後からデバッグしやすくなります。 |
|||
| No.1594 |
Re:ダイクストラ法を使った最短経路 投稿者---deer(2004/04/16 19:57:44) |
||
えと、コンパイルの際、エラーメッセージがたくさん出るとのことでしたが、 私がコンパイルした際は全く出ません。 警告さえ。 環境の違いでしょうか。 私は、UNIX上で動かしていますが。 グローバル変数についてですが、 関数の引渡しが不安だったので、思わずグローバルで取ってしまいました。 やはり、あまりよくないですよね。 ちょっと改良してみたいと思います。 |
|||
| No.1595 |
Re:ダイクストラ法を使った最短経路 投稿者---たか(2004/04/16 20:58:12) |
||
>えと、コンパイルの際、エラーメッセージがたくさん出るとのことでしたが、 >私がコンパイルした際は全く出ません。 >警告さえ。 >環境の違いでしょうか。 >私は、UNIX上で動かしていますが。 コンパイルエラーと警告について若干の混同がありました。エラーは出て いませんでした。済みません。 しかし、 C:/mingw/dijkatra_1.c: In function `Report_answer': C:/mingw/dijkatra_1.c:78: warning: char format, different type arg (arg 2) C:/mingw/dijkatra_1.c:85: warning: char format, different type arg (arg 2) C:/mingw/dijkatra_1.c:90: warning: char format, different type arg (arg 2) C:/mingw/dijkatra_1.c:95: warning: char format, different type arg (arg 2) C:/mingw/dijkatra_1.c:70: warning: unused variable `city' C:/mingw/dijkatra_1.c: In function `Build_graph': C:/mingw/dijkatra_1.c:142: warning: no return statement in function returning non-void C:/mingw/dijkatra_1.c:142: warning: control reaches end of non-void function C:/mingw/dijkatra_1.c: At top level: C:/mingw/dijkatra_1.c:145: warning: `main' takes only zero or two arguments C:/mingw/dijkatra_1.c: In function `main': C:/mingw/dijkatra_1.c:162: warning: control reaches end of non-void function Execution terminated とかなり派手に警告が出て、致命的なコンパイルエラーがないのに実行 形式を作成しませんでした。gcc3.3.3(MinGW)です。-Wallはやり過ぎで しょうか。ただgccはscanfやprintfの書式文字列と引数の型を照合する 独特な警告検出機構を持っており、有意義に使っています。 >グローバル変数についてですが、 >関数の引渡しが不安だったので、思わずグローバルで取ってしまいました。 >やはり、あまりよくないですよね。 >ちょっと改良してみたいと思います。 この規模程度でしたらまだ大丈夫かと思いますが、これ以上プログラムが 大きくなってくると大域変数に絡むバグが忍び込みやすくなります。 大域変数絡みのバグ、メモリリークのバグはなかなか厄介です。特にメモ リリークが起きると、プログラム全体の形を保ったままバグ取りするのは ほとんど不可能になります。大まかにプログラム全体を書いて後からバグ 潰しをする方法と、書く段階で既にバグが潜在化しにくい書き方をするの とでは、雲泥の差になる事があります。 長々と書いてすみません。以前プログラムのキャッチボールをしていて ついに完成に至らず放置になった事がありましたので引っかかっています。 |
|||
| No.1596 |
Re:ダイクストラ法を使った最短経路 投稿者---deer(2004/04/16 22:27:06) |
||
私のほうだと、あまり、警告等々がでないようです。 そのくらい出てもらえると、 間違いに気づきやすく、後々よさそうな気がします。 ところで、この間たかさんに投稿していただいたプログラムなのですが、 No route from ・・・ to ・・・. のところで、 どうしても文字化けをしてしまうのです。 それはなぜなのでしょうか。 また、endingcityがリスト上にない場合に、もう一度入力を促すようにしたはずなのですが、 どうしても、普通に処理してしまいます。 たとえば、 Start City (Q to quit) : venice There is no venice on the data. Ending City : nottingham There is no nottingham on the data. Shortest Route : ÿÿÿÿ Total Distance : 0 このように。 この場合、Shortest Routeも化けてますが･･･。 それは、何が原因でこうなるのでしょうか。 |
|||
| No.1597 |
Re:ダイクストラ法を使った最短経路 投稿者---deer(2004/04/16 22:53:17) |
||
> >ところで、この間たかさんに投稿していただいたプログラムなのですが、 >No route from ・・・ to ・・・. >のところで、 >どうしても文字化けをしてしまうのです。 >それはなぜなのでしょうか。 > >また、endingcityがリスト上にない場合に、もう一度入力を促すようにしたはずなのですが、 >どうしても、普通に処理してしまいます。 >たとえば、 >Start City (Q to quit) : venice >There is no venice on the data. >Ending City : nottingham >There is no nottingham on the data. >Shortest Route : ÿÿÿÿ >Total Distance : 0 >このように。 >この場合、Shortest Routeも化けてますが･･･。 >それは、何が原因でこうなるのでしょうか。 化けるのは、リストにないからですね。その都市名が。笑 単純なことでした･･･。 |
|||
| No.1598 |
Re:ダイクストラ法を使った最短経路 投稿者---たか(2004/04/16 23:25:46) |
||
よく見るといつの間にか変な所に不要な break; が入ってしまってます ね。ソースを修正する時に新たなバグを入れてしまうとご自分で直せなく なってしまいますから、十分注意して下さい。 while(1){
while(1){
printf("\nStart City (Q to quit) : ");
scanf("%s", &startcitybuf);
if(*startcitybuf == 'Q' || *startcitybuf == 'q'){
exit(0);
}
startcity = checkcity(startcitybuf, n);
if(startcity != 0)
break;
printf("There is no %s on the data.\n", &startcitybuf);
/* break; */
}
while(1){
printf("Ending City : ");
scanf("%s", &endingcitybuf);
endingcity = checkcity(endingcitybuf, n);
if(endingcity != 0)
break;
printf("There is no %s on the data.\n", &endingcitybuf);
/* break; */
}
|
|||
| No.1599 |
Re:ダイクストラ法を使った最短経路 投稿者---たか(2004/04/16 23:28:38) |
||
それはそうとして、もしお使いのコンパイラがgccでしたら、-Wall オプションを付けてコンパイルされる事を強く推奨します。gccの警告 機能はかなり強力で、潜在的なバグを見つけてくれる事もあります。 |
|||
| No.1600 |
Re:ダイクストラ法を使った最短経路 投稿者---deer(2004/04/19 08:13:50) |
||
>それはそうとして、もしお使いのコンパイラがgccでしたら、-Wall >オプションを付けてコンパイルされる事を強く推奨します。gccの警告 >機能はかなり強力で、潜在的なバグを見つけてくれる事もあります。 いろいろ、ありがとうございました。 無事に完成することができました！！ コンパイラはgccを使っていました。 次から、-Wallをつけて使ってみようと思います。 いろいろ勉強になりました。 本当にありがとうございました。 |
|||