最短経路の求め方

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

最短経路の求め方

#1

投稿記事 by tui » 3ヶ月前

実現したいこと

それぞれの頂点からの最短経路をダイクストラ法により出力したい
発生しているエラー

エラーはありません


試してたいこと

jを用いているループのなかで4回目以降で最短経路ではない場所に行ってしまいます。

そこの処理にかんしてアドバイスいただきたいです。
よろしくお願いします。

補足情報

Windows10
visualstdio

各頂点を訪れた際の処理に誤りがあるのではないかと思っています。

コード:

#include<stdio.h>
#define max 1000000
#define N 7

void print_matrix(int a[][N]);

int main(void){

  int distance[N],visited[N],route[N],count_t[N];
  int i,j,k,count,min,now,temp;

  int matrix[N][N] = {
    { 0 , 17,max,max,max,max,max},
    { 17, 0 , 21, 7 ,max,max,max},
    {max, 21, 0 , 13, 5 ,max,max},
    {max, 7 , 13, 0 ,max, 5 ,max},
    {max,max, 5 ,max, 0 , 16, 22},
    {max,max,max, 5 , 16, 0 , 25},
    {max,max,max,max, 22, 25, 0 }};

  for(i=0;i<N;i++){
    visited[i] = 0; distance[i] = max; route[i] = -1 ; count_t[i] = 0;
  }

  print_matrix(matrix);

  //初期化を行う
  visited[0] = 1;distance[0] = 0;
  now = j = k = 0; min = max;

  for(j = 0;j <  5;j++){

    printf("---------------------------------------------------------------\n");
    printf("now = %d\n",now);
    count_t[j] = now; 
    for(i=0;i<N;i++){
      printf(" %6d ",distance[i]);
    }

    printf("\n");

    for(i=0;i<N;i++){
      printf(" %6d ",visited[i]);
    }

    printf("\n");

    for(i=0;i<N;i++){
      printf(" %6d ",route[i]);
    }

    printf("\n");

    // visited[now] = 1;
    for(i=0;i<N;i++){
    if(matrix[now][i] < max && visited[i] ==0 && matrix[now][i] > 0){
      // distance[i] = matrix[now][i] + distance[now];
      temp = matrix[now][i] + distance[now];
      if(temp < distance[i]){
    distance[i] = temp;
      }

      if(min > distance[i] && visited[i] == 0){
      min = distance[i]; count = i; route[i] = now;
      }
      }      


    }
    visited[count]++;  now=count; min = max;
    //count_t[j] = now;
  }

  /*
  printf("---------------------------------------\n"); 
  printf("4までの最短経路は\n");
  for(i = 0;i < N;i++){
    printf("%d>>",count_t[i]);
  }
  printf("終了\n");
  printf("---------------------------------------\n"); 
  */
}
//行列を表示する関数
void print_matrix(int a[][N])
{
  int i, j;

  for(i=0;i<N;i++) {
    for(j=0;j<N;j++){
      printf("%8d ", a[i][j]);}
    printf("\n");
  }
  return;
}


アバター
みけCAT
記事: 6120
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: 最短経路の求め方

#2

投稿記事 by みけCAT » 3ヶ月前

まず、処理対象のグラフを図示してみました。
graph.png
グラフ
graph.png (12.42 KiB) 閲覧数: 332 回
Wandboxで実行してみると、以下のようになりました。

コード:

       0       17  1000000  1000000  1000000  1000000  1000000 
      17        0       21        7  1000000  1000000  1000000 
 1000000       21        0       13        5  1000000  1000000 
 1000000        7       13        0  1000000        5  1000000 
 1000000  1000000        5  1000000        0       16       22 
 1000000  1000000  1000000        5       16        0       25 
 1000000  1000000  1000000  1000000       22       25        0 
---------------------------------------------------------------
now = 0
      0  1000000  1000000  1000000  1000000  1000000  1000000 
      1       0       0       0       0       0       0 
     -1      -1      -1      -1      -1      -1      -1 
---------------------------------------------------------------
now = 1
      0      17  1000000  1000000  1000000  1000000  1000000 
      1       1       0       0       0       0       0 
     -1       0      -1      -1      -1      -1      -1 
---------------------------------------------------------------
now = 3
      0      17      38      24  1000000  1000000  1000000 
      1       1       0       1       0       0       0 
     -1       0       1       1      -1      -1      -1 
---------------------------------------------------------------
now = 5
      0      17      37      24  1000000      29  1000000 
      1       1       0       1       0       1       0 
     -1       0       3       1      -1       3      -1 
---------------------------------------------------------------
now = 4
      0      17      37      24      45      29      54 
      1       1       0       1       1       1       0 
     -1       0       3       1       5       3      -1 
不都合の原因は、今いる頂点から辺がある頂点にしか行かないようにしていることですね。
インデントが乱れてブロックの入れ子関係がわかりにくくなっているので、整えるといいでしょう。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

tui

Re: 最短経路の求め方

#3

投稿記事 by tui » 3ヶ月前

その頂点の処理に関してどのように変えたらいいかアドバイスいただけませんか?

かずま

Re: 最短経路の求め方

#4

投稿記事 by かずま » 3ヶ月前

tui さんが書きました:
3ヶ月前
その頂点の処理に関してどのように変えたらいいかアドバイスいただけませんか?
・j のループを 5回から N回に変更。
・最初の if の式から && visited[ i] == 0 を削除。
・route[ i] = now; を 3番目の if文から 2番目の if文に移動。
・未使用変数を削除。
・インデント改善。

コード:

#include <stdio.h>

#define max 1000000
#define N 7

void print_matrix(int a[][N]);

int main(void)
{
	int distance[N], visited[N], route[N];  // count_t を削除
	int i, j, count, min, now, temp;        // k を削除

	int matrix[N][N] = {
		{ 0 , 17,max,max,max,max,max},
		{ 17, 0 , 21, 7 ,max,max,max},
		{max, 21, 0 , 13, 5 ,max,max},
		{max, 7 , 13, 0 ,max, 5 ,max},
		{max,max, 5 ,max, 0 , 16, 22},
		{max,max,max, 5 , 16, 0 , 25},
		{max,max,max,max, 22, 25, 0 }
	};

	for (i = 0; i < N; i++) {
		visited[i] = 0; distance[i] = max; route[i] = -1;
	}
	print_matrix(matrix);

	//初期化を行う
	visited[0] = 1; distance[0] = 0;
	now = 0; min = max;

	for (j = 0; j < N; j++) {           // 5 を N に変更
		printf("---------------------------------------------------------------\n");
		printf("now = %d\n",now);
		for (i = 0; i < N; i++) {
			printf(" %6d ", distance[i]);
		}
		printf("\n");

		for (i = 0; i < N; i++) {
			printf(" %6d ", visited[i]);
		}
		printf("\n");

		for (i = 0; i < N; i++) {
			printf(" %6d ", route[i]);
		}
		printf("\n");

		for (i = 0; i < N;i++) {
			if (matrix[now][i] < max && matrix[now][i] > 0) { // visited削除
				temp = matrix[now][i] + distance[now];
				if (temp < distance[i]){
					distance[i] = temp;
					route[i] = now;      // 追加
				}

				if (min > distance[i] && visited[i] == 0) {
					min = distance[i]; count = i;  // route を削除
				}
			}			
		}
		visited[count]++; now = count; min = max;
	}
}
//行列を表示する関数
void print_matrix(int a[][N])
{
	int i, j;

	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			printf("%8d ", a[i][j]);
		}
		printf("\n");
	}
}
実行結果

コード:

       0       17  1000000  1000000  1000000  1000000  1000000 
      17        0       21        7  1000000  1000000  1000000 
 1000000       21        0       13        5  1000000  1000000 
 1000000        7       13        0  1000000        5  1000000 
 1000000  1000000        5  1000000        0       16       22 
 1000000  1000000  1000000        5       16        0       25 
 1000000  1000000  1000000  1000000       22       25        0 
---------------------------------------------------------------
now = 0
      0  1000000  1000000  1000000  1000000  1000000  1000000 
      1       0       0       0       0       0       0 
     -1      -1      -1      -1      -1      -1      -1 
---------------------------------------------------------------
now = 1
      0      17  1000000  1000000  1000000  1000000  1000000 
      1       1       0       0       0       0       0 
     -1       0      -1      -1      -1      -1      -1 
---------------------------------------------------------------
now = 3
      0      17      38      24  1000000  1000000  1000000 
      1       1       0       1       0       0       0 
     -1       0       1       1      -1      -1      -1 
---------------------------------------------------------------
now = 5
      0      17      37      24  1000000      29  1000000 
      1       1       0       1       0       1       0 
     -1       0       3       1      -1       3      -1 
---------------------------------------------------------------
now = 4
      0      17      37      24      45      29      54 
      1       1       0       1       1       1       0 
     -1       0       3       1       5       3       5 
---------------------------------------------------------------
now = 2
      0      17      37      24      45      29      54 
      1       1       1       1       1       1       0 
     -1       0       3       1       5       3       5 
---------------------------------------------------------------
now = 2
      0      17      37      24      42      29      54 
      1       1       2       1       1       1       0 
     -1       0       3       1       2       3       5 

かずま

Re: 最短経路の求め方

#5

投稿記事 by かずま » 3ヶ月前

visited[6] が 1 にならないので、次のように修正します。

コード:

		for (i = 0; i < N;i++) {
			if (matrix[now][i] < max && matrix[now][i] > 0) { // visited削除
				temp = matrix[now][i] + distance[now];
				if (temp < distance[i]){
					distance[i] = temp;
					route[i] = now;      // 追加
				}
			}			
			if (min > distance[i] && visited[i] == 0) {
				min = distance[i]; count = i;  // route を削除
			}
		}
3番目の if文を、1番目の if文の中から外に出しました。
これでよろしいでしょうか?

かずま

Re: 最短経路の求め方

#6

投稿記事 by かずま » 3ヶ月前

各頂点への最短経路は、main の最後に次のコードを追加してください。

コード:

	for (i = 1; i < N; i++) {
		j = i;
		do {
			printf(" %d <-", j);
			j = route[j];
		} while (j);
		printf(" 0\n");
	}
}
実行結果

コード:

 1 <- 0
 2 <- 3 <- 1 <- 0
 3 <- 1 <- 0
 4 <- 2 <- 3 <- 1 <- 0
 5 <- 3 <- 1 <- 0
 6 <- 5 <- 3 <- 1 <- 0
逆順になっています。

かずま

Re: 最短経路の求め方

#7

投稿記事 by かずま » 3ヶ月前

各頂点への最短経路を、出発点 0 から順に表示したければ、

コード:

void print_route(const int *route, int i)
{
	if (i) print_route(route, route[i]);
	printf(" %d ->", i);
}

int main(void)
{
	...
	for (i = 1; i < N; i++) {
		print_route(route, route[i]);
		printf(" %d\n", i);
	}
}
実行結果

コード:

 0 -> 1
 0 -> 1 -> 3 -> 2
 0 -> 1 -> 3
 0 -> 1 -> 3 -> 2 -> 4
 0 -> 1 -> 3 -> 5
 0 -> 1 -> 3 -> 5 -> 6

naohiro19
記事: 256
登録日時: 8年前
住所: 愛知県

Re: 最短経路の求め方

#8

投稿記事 by naohiro19 » 3ヶ月前

Boost.GraphというC++のライブラリがあります。

コード:

#include <iostream>[attachment=0]path.png[/attachment]
#include <vector>
#include <deque>
#include <string>
#include <boost/assign/list_of.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

using namespace std;
using namespace boost;
using namespace boost::assign;

typedef adjacency_list < vecS, vecS, undirectedS,
	no_property, property<edge_weight_t, int> > Graph;
typedef pair<int, int> Edge;
typedef graph_traits<Graph>::vertex_descriptor Vertex;

enum { A, B, C, D, E, F, G, N };
const string Name = "ABCDEFG";

Graph make_graph()
{
	const vector<Edge> edges = list_of<Edge>
		(A,B)(B,C)
		(B,D)(C,E)
		(E,F)(D,F)
		(C,D)(E,G)
		(F,G)
	;
	const vector<int> weights = list_of
		(17)(21)
		(7)(5)
		(16)(5)
		(13)(22)
		(25)
	;
	return Graph(edges.begin(), edges.end(), weights.begin(), N);
}

int main()
{
	const Graph g = make_graph();
	const Vertex from = A;
	const Vertex to = G;

	// 最短経路を計算
	vector<Vertex> parents(num_vertices(g));
	dijkstra_shortest_paths(g, from,
		predecessor_map(&parents[0]));

	// 経路なし
	if(parents[to] == to){
		cout << "経路が見つかりません" << endl;
		return 1;
	}

	// 最短経路の頂点リストを作成
	deque<Vertex> route;
	for(Vertex v = to; v != from; v = parents[v]){
		route.push_front(v);
	}
	route.push_front(from);

	// 最短経路を出力
	for(const Vertex v: route){
		cout << Name[v] << endl;
	}
}

出力:
A
B
D
F
G

このグラフの場合、A→B→D→F→Gの順番に頂点を辿れば最短距離となります。
添付ファイル
path.png
graphviz形式で出力してpngファイルに変換しました。
path.png (24.18 KiB) 閲覧数: 225 回

かずま

Re: 最短経路の求め方

#9

投稿記事 by かずま » 3ヶ月前

for文の中の 3つの if文ですが、最初の if文は要りませんね。

コード:

#include <stdio.h>

#define MAX  999999
#define N    7

void print_array(const int *a)
{
	for (int i = 0; i < N; i++) printf("%7d ", a[i]);
	putchar('\n');
}

void print_matrix(int a[][N])
{
	for (int i = 0; i < N; i++) print_array(a[i]);
}

void print_route(const int *route, int i)
{
	if (i) print_route(route, route[i]);
	printf(" %d ->", i);
}

int main(void)
{
	int matrix[N][N] = {
		{   0,  17, MAX, MAX, MAX, MAX, MAX },
		{  17,  0 ,  21,  7 , MAX, MAX, MAX },
		{ MAX,  21,   0,  13,   5, MAX, MAX },
		{ MAX,  7 ,  13,   0, MAX,   5, MAX },
		{ MAX, MAX,   5, MAX,   0,  16,  22 },
		{ MAX, MAX, MAX,   5,  16,   0,  25 },
		{ MAX, MAX, MAX, MAX,  22,  25,   0 },
	};
	print_matrix(matrix);

	int now = 0, visited[N] = { 1 }, distance[N] = { 0 }, route[N] = { 0 };
	for (int i = 1; i < N; i++) distance[i] = MAX;

	for (int j = 0; j < N; j++) {
		printf("---------------------------------------------------------\n"
		       "now = %d\n", now);
		print_array(distance), print_array(visited), print_array(route);

		int k, min = MAX;
		for (int i = 0; i < N; i++) {
			int temp = matrix[now][i] + distance[now];
			if (temp < distance[i]) distance[i] = temp, route[i] = now;
			if (distance[i] < min && !visited[i]) min = distance[i], k = i;
		}
		now = k, visited[now] = 1;
	}
	puts("---------------------------------------------------------");
	for (int i = 1; i < N; i++)
		print_route(route, route[i]), printf(" %d\n", i);
}
分からないところは質問してください。

返信

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