ページ 11

最短経路の求め方

Posted: 2019年1月22日(火) 12:28
by tui
実現したいこと

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

エラーはありません


試してたいこと

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;
}


Re: 最短経路の求め方

Posted: 2019年1月22日(火) 19:16
by みけCAT
まず、処理対象のグラフを図示してみました。
graph.png
グラフ
graph.png (12.42 KiB) 閲覧数: 3902 回
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 
不都合の原因は、今いる頂点から辺がある頂点にしか行かないようにしていることですね。
インデントが乱れてブロックの入れ子関係がわかりにくくなっているので、整えるといいでしょう。

Re: 最短経路の求め方

Posted: 2019年1月23日(水) 02:18
by tui
その頂点の処理に関してどのように変えたらいいかアドバイスいただけませんか?

Re: 最短経路の求め方

Posted: 2019年1月23日(水) 17:32
by かずま
tui さんが書きました:
5年前
その頂点の処理に関してどのように変えたらいいかアドバイスいただけませんか?
・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: 最短経路の求め方

Posted: 2019年1月23日(水) 18:06
by かずま
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: 最短経路の求め方

Posted: 2019年1月23日(水) 18:32
by かずま
各頂点への最短経路は、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: 最短経路の求め方

Posted: 2019年1月23日(水) 21:19
by かずま
各頂点への最短経路を、出発点 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

Re: 最短経路の求め方

Posted: 2019年1月24日(木) 09:23
by naohiro19
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の順番に頂点を辿れば最短距離となります。

Re: 最短経路の求め方

Posted: 2019年1月25日(金) 03:56
by かずま
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);
}
分からないところは質問してください。