最短経路の求め方

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

トピックに返信する


答えを正確にご入力ください。答えられるかどうかでスパムボットか否かを判定します。
BBCode: ON
[img]: ON
[flash]: OFF
[url]: ON
スマイリー: OFF
トピックのレビュー
   

展開ビュー トピックのレビュー: 最短経路の求め方

Re: 最短経路の求め方

#9

by かずま » 5年前

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);
}
分からないところは質問してください。

Re: 最短経路の求め方

#8

by naohiro19 » 5年前

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) 閲覧数: 4346 回

Re: 最短経路の求め方

#7

by かずま » 5年前

各頂点への最短経路を、出発点 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: 最短経路の求め方

#6

by かずま » 5年前

各頂点への最短経路は、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: 最短経路の求め方

#5

by かずま » 5年前

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: 最短経路の求め方

#4

by かずま » 5年前

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: 最短経路の求め方

#3

by tui » 5年前

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

Re: 最短経路の求め方

#2

by みけCAT » 5年前

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

最短経路の求め方

#1

by tui » 5年前

実現したいこと

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

エラーはありません


試してたいこと

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

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

補足情報

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("４までの最短経路は\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;
}

ページトップ