質問編集履歴

ダイクストラ法のアルゴリズムにするためにプログラムを変えました。

2021/11/15 21:15

投稿

wagashi_157

スコア51

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -64,6 +64,8 @@
 #define N		30
+#define DENSITY		9
 #define MAX_COST	100
@@ -76,6 +78,14 @@
 };
+struct to_len {
+        int to, len;
+};
+list<to_len> vList[N];
 node node_data[N];
@@ -124,6 +134,64 @@
+void down_heap(int parent)
+{
+	if (left(parent)>heap_size-1) return;
+	if (left(parent)==heap_size-1) {
+		if (node_data[parent].cost>node_data[left(parent)].cost) {
+			node_idx[node_data[parent].id] = left(parent);
+			node_idx[node_data[left(parent)].id] = parent;
+			swap(node_data[parent],node_data[left(parent)]);
+			down_heap(left(parent));
+		}
+	} else {
+		if (node_data[left(parent)].cost<=node_data[right(parent)].cost) {
+			if (node_data[parent].cost>node_data[left(parent)].cost) {
+				node_idx[node_data[parent].id] = left(parent);
+				node_idx[node_data[left(parent)].id] = parent;
+				swap(node_data[parent],node_data[left(parent)]);
+				down_heap(left(parent));
+			}
+		} else {
+			if (node_data[parent].cost>node_data[right(parent)].cost) {
+				node_idx[node_data[parent].id] = right(parent);
+				node_idx[node_data[right(parent)].id] = parent;
+				swap(node_data[parent],node_data[right(parent)]);
+				down_heap(right(parent));
+			}
+		}
+	}
+}
 void up_heap(int child)
 {
@@ -184,17 +252,17 @@
 }
 void make_heap()
 {
+	for (int i=(N-1)/2; i>=0; i--) {
-	up_heap(N-1);
+		down_heap(i);
-}
+	}
+}
 bool check_rightmost(int i)
@@ -214,36 +282,6 @@
 }
-void print_heap()
-{
-	for (int i=0; i<heap_size; i++) {
-		cout << "id: ";
-		cout << node_data[i].id;
-		cout << ", cost: ";
-		cout << node_data[i].cost;
-		if (check_rightmost(i)) cout << endl;
-		else cout << "   ";
-	}
-	cout << endl;
-}
 void push(int id, int cost)
 {
@@ -294,85 +332,77 @@
 }
 void change(int id, int cost)
 {
+	int old;
+	old=node_data[node_idx[id]].cost;
 	node_data[node_idx[id]].cost=cost;
-	node_idx[node_data[node_idx[id]].id]=id;
+	if (old>node_data[node_idx[id]].cost) down_heap(node_idx[id]);
+	else up_heap(node_idx[id]);
-}
+}
+void print_path()
+{
+	if (path[N-1] == -1)
+		cout << "Unreachable!" << endl;
+	else {
+		rec_print_path(N-1);
+		cout << endl;
+		cout << "cost: " << node_data[0].cost << endl;
+	}
+}
+void rec_print_path(int vertex)
+{
+	path[0]=1;
+	for (auto next:graph[vertex]) {
+		if (path[next]==1) continue;
+		rec_print_path(next);
+	}
+}
 int main()
 {
-	gen_node_data();
+	gen_graph();
-	print_heap();
+	print_graph();
-	make_heap();
-	print_heap();
+	init_heap();
-	int op, id, cost;
-	while (cout << "Input an operation number: 1:push, 2:pop, 3:change -> "
-	&& cin >> op) {
-		switch (op) {
+	dijkstra();
-		case 1: // push
-			cout << "Input an ID number -> ";
-			cin >> id;
-			cout << "Input its cost -> ";
-			cin >> cost;
-			push(id, cost);
-			break;
-		case 2: // pop
-			pop();
-			break;
-		case 3: // change
-			cout << "Input an ID number -> ";
-			cin >> id;
-			cout << "Input its cost -> ";
-			cin >> cost;
-			change(id, cost);
-			break;
-		default:
-			cout << "Input 1, 2, or 3." << endl;
-		}
-		print_heap();
+	print_path();
-	}

プログラムを修正しました。

2021/11/15 21:15

投稿

wagashi_157

スコア51

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -58,23 +58,13 @@
 #include<random>
-#include<list>
 using namespace std;
 #define N		30
-#define DENSITY		9
-#define MAX_COST	10
+#define MAX_COST	100
-int graph[N][N]={0};
-int path[N]={0};
@@ -88,16 +78,6 @@
-struct to_len {
-        int to, len;
-};
-list<to_len> vList[N];
 node node_data[N];
 int node_idx[N];
@@ -106,365 +86,293 @@
-void gen_graph()
+void gen_node_data()
 {
 	mt19937 mt{random_device{}()};
-	uniform_int_distribution<int> dist(0,DENSITY);
-	uniform_int_distribution<int> wdist(1,MAX_COST);
+	uniform_int_distribution<int> dist(0,MAX_COST);
-	int len;
+	heap_size = 0;
-	for (int i=0; i<N; i++)
+	for (int i=0; i<N; i++) {
-		for (int j=i+1; j<N; j++)
+		node_data[i].id = i;
-			graph[i][j] = dist(mt);
+		node_data[i].cost = dist(mt);
+		heap_size++;
+		node_idx[i] = i;
+	}
+}
-	for (int i=0; i<N; i++)
+int left(int i) {return 2*i+1;}
-		for (int j=i+1; j<N; j++)
+int right(int i) {return 2*i+2;}
+void swap(node &a, node &b) {node tmp=a; a=b; b=tmp;}
+void up_heap(int child)
+{
+	int parent=(child-1)/2;
+	if (child>heap_size-1) return;
-			if (graph[i][j]==1) {
+	if (child==heap_size-1) {
+		if (node_data[parent].cost<node_data[child].cost) {
+			node_idx[node_data[parent].id] = child;
+			node_idx[node_data[child].id] = parent;
+			swap(node_data[parent],node_data[child]);
-				len = wdist(mt);
+			up_heap(parent);
+		}
+	} else {
+		if (node_data[right(parent)].cost<=node_data[left(parent)].cost) {
+			if (node_data[left(parent)].cost>node_data[parent].cost) {
+				node_idx[node_data[parent].id] = left(parent);
+				node_idx[node_data[left(parent)].id] = parent;
+				swap(node_data[parent],node_data[left(parent)]);
-				vList[i].push_back({j,len});
+				up_heap(parent);
-				vList[j].push_back({i,len});
 			}
+		} else {
+			if (node_data[right(parent)].cost>node_data[parent].cost) {
-	for (int i=0; i<N; i++)
+				node_idx[node_data[parent].id] = right(parent);
+				node_idx[node_data[right(parent)].id] = parent;
+				swap(node_data[parent],node_data[right(parent)]);
-		path[i] = -1;
+				up_heap(parent);
-}
+			}
-int left(int i) {return 2*i+1;}
-int right(int i) {return 2*i+2;}
-void swap(node &a, node &b) {node tmp=a; a=b; b=tmp;}
-void down_heap(int parent)
-{
-	if (left(parent)>heap_size-1) return;
-	if (left(parent)==heap_size-1) {
-		if (node_data[parent].cost>node_data[left(parent)].cost) {
-			node_idx[node_data[parent].id] = left(parent);
-			node_idx[node_data[left(parent)].id] = parent;
-			swap(node_data[parent],node_data[left(parent)]);
-			down_heap(left(parent));
 		}
-	} else {
-		if (node_data[left(parent)].cost<=node_data[right(parent)].cost) {
-			if (node_data[parent].cost>node_data[left(parent)].cost) {
-				node_idx[node_data[parent].id] = left(parent);
-				node_idx[node_data[left(parent)].id] = parent;
-				swap(node_data[parent],node_data[left(parent)]);
-				down_heap(left(parent));
-			}
-		} else {
-			if (node_data[parent].cost>node_data[right(parent)].cost) {
-				node_idx[node_data[parent].id] = right(parent);
-				node_idx[node_data[right(parent)].id] = parent;
-				swap(node_data[parent],node_data[right(parent)]);
-				down_heap(right(parent));
-			}
+	}
+}
+void make_heap()
+{
+	up_heap(N-1);
+}
+bool check_rightmost(int i)
+{
+	int x = i+2;
+	while (x>1) {
+		if (x%2==1) return 0;
+		else x=x/2;
+	}
+	return 1;
+}
+void print_heap()
+{
+	for (int i=0; i<heap_size; i++) {
+		cout << "id: ";
+		cout << node_data[i].id;
+		cout << ", cost: ";
+		cout << node_data[i].cost;
+		if (check_rightmost(i)) cout << endl;
+		else cout << "   ";
+	}
+	cout << endl;
+}
+void push(int id, int cost)
+{
+	for (int i=0; i<N-1; i++) {
+		node_data[i].id=node_data[i+1].id;
+		node_data[i].cost=node_data[i+1].cost;
+	}
+	for (int i=0; i<N-1; i++) {
+		node_idx[node_data[i].id]=node_data[i].id;
+	}
+	node_data[N-1].id=id;
+	node_data[N-1].cost=cost;
+	node_idx[node_data[N-1].id]=node_data[N-1].id;
+}
+void pop()
+{
+	for (int i=0; i<N-1; i++) {
+		node_data[i].id=node_data[i+1].id;
+		node_data[i].cost=node_data[i+1].cost;
+	}
+	for (int i=0; i<N-1; i++) {
+		node_idx[node_data[i].id]=node_data[i].id;
+	}
+	node_idx[node_data[N-1].id]=node_data[N-1].id;
+}
+void change(int id, int cost)
+{
+	node_data[node_idx[id]].cost=cost;
+	node_idx[node_data[node_idx[id]].id]=id;
+}
+int main()
+{
+	gen_node_data();
+	print_heap();
+	make_heap();
+	print_heap();
+	int op, id, cost;
+	while (cout << "Input an operation number: 1:push, 2:pop, 3:change -> "
+	&& cin >> op) {
+		switch (op) {
+		case 1: // push
+			cout << "Input an ID number -> ";
+			cin >> id;
+			cout << "Input its cost -> ";
+			cin >> cost;
+			push(id, cost);
+			break;
+		case 2: // pop
+			pop();
+			break;
+		case 3: // change
+			cout << "Input an ID number -> ";
+			cin >> id;
+			cout << "Input its cost -> ";
+			cin >> cost;
+			change(id, cost);
+			break;
+		default:
+			cout << "Input 1, 2, or 3." << endl;
 		}
+		print_heap();
-	}
+	}
-}
-void up_heap(int child)
-{
-	int t;
-	while (child>0) {
-		if (node_idx[child/2]>node_idx[child]) {
-			t=node_idx[child/2];
-			node_idx[child/2]=node_idx[child];
-			node_idx[child]=t;
-		}
-		child=child/2;
-	}
-}
-void init_heap()
-{
-	node_data[0].id = 0;
-	node_data[0].cost = 0;
-	heap_size = 1;
-	for (int i=1; i<N; i++) {
-		node_data[i].id = i;
-		node_data[i].cost = MAX_COST*N;
-		heap_size++;
-		node_idx[i] = i;
-	}
-}
-void push(int id, int cost)
-{
-	for (int i=0; i<N-1; i++) {
-		node_data[i].id=node_data[i+1].id;
-		node_data[i].cost=node_data[i+1].cost;
-	}
-	node_data[N-1].id=id;
-	node_data[N-1].cost=cost;
-}
-void pop()
-{
-	for (int i=0; i<N-1; i++) {
-		node_data[i].id=node_data[i+1].id;
-		node_data[i].cost=node_data[i+1].cost;
-	}
-	node_data[N-1].id=0;
-	node_data[N-1].cost=0;
-}
-void change(int id, int cost)
-{
-	node_data[node_idx[id]].cost=cost;
-}
-void dijkstra()
-{
-	int s,j,minlen,m;
-	for (j=0; j<N; j++) {
-		for (auto it{vList[m].begin()}; it!=vList[m].end(); ++it) {
-			path[j]=9999;
-			s=0;
-			(*it).len=0;
-		}
-	}
-	for (m=0; m<N; m++) {
-		path[s]=1;
-		for (auto it{vList[m].begin()}; it!=vList[m].end(); ++it) {
-			if (graph[s][j]!=1) continue;
-			if ((*it).len+graph[s][j]<(*it).len) (*it).len=(*it).len+graph[it][j];
-		}
-		minlen=9999;
-		for (auto it{vList[m].begin()}; it!=vList[m].end(); ++it) {
-			if (path[j]==1) continue;
-			if ((*it).len<minlen) {minlen=j; it=j;}
-		}
-	}
-}
-void print_graph()
-{
-	for (int i=0; i<N; i++) {
-		for (int j=0; j<N; j++)
-			cout << (graph[i][j]!=0) << " ";
-		cout << endl;
-	}
-	cout << endl;
-	for (int i=0; i<N; i++) {
-		cout << i << ": ";
-		for (auto itr=vList[i].begin(); itr!=vList[i].end(); ++itr)
-			cout << (*itr).to << " ";
-			cout << endl;
-	}
-	cout << endl;
-}
-void rec_print_path(int vertex)
-{
-	path[0]=1;
-	for (auto next:graph[vertex]) {
-		if (path[next]==1) continue;
-		rec_print_path(next);
-	}
-}
-void print_path()
-{
-	if (path[N-1] == -1)
-		cout << "Unreachable!" << endl;
-	else {
-		rec_print_path(N-1);
-		cout << endl;
-		cout << "cost: " << node_data[0].cost << endl;
-	}
-}
-int main()
-{
-	gen_graph();
-	print_graph();
-	init_heap();
-	dijkstra();
-	print_path();
@@ -472,6 +380,8 @@
 }
 ```
 ### 試したこと

pop,push,changeは解決できたのでdijkstra関数や到達可能を判定するためのプログラムを解決したいということを追記しました。

2021/11/15 10:06

投稿

wagashi_157

スコア51

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -1,6 +1,6 @@
 ### 前提・実現したいこと
-以下の要領にしたがって優先度付きキューを適切に利用したダイクストラ法のアルゴリズムを実装したいです。
+以下の要領を基に優先度付きキューを適切に利用したダイクストラ法のアルゴリズムを実装しようと思っています。
 1. まず，３０個の頂点上のグラフを保持する二次元配列graph[N][N]，及び，その隣接リストvList[N]，更に，最短経路木を保持する一次元配列path[N] を（大域変数として）用意する．
@@ -14,196 +14,42 @@
 ### 発生している問題・エラーメッセージ
-popやpushのうち構造体の扱い方でエラーが出ており, 到達可能を始めから順に出力するためのrec_print_pathの表現の仕方が分からず困っています。
+push,pop,changeのプログラムは解決できましたが, 到達可能を判定するためのrec_print_pathの表現の仕方が分からず困っています(print_pathにもあるようにvoid関数で実装したいです)。それとlist関数を使ってdijkstra()を実装したいのですが, イテレータで表現してもエラーが出てしまい, 原因が分かりません。イテレーターに慣れていないのとダイクストラ法で図は描けるもののプログラムとなると中々上手くいかないので教えてほしいです。
 ```
-dijkstra.cpp: 関数 ‘void down_heap(int)’ 内:
-dijkstra.cpp:52:17: エラー: invalid initialization of reference of type ‘std::ios_base&’ from expression of type ‘int’
-  if (left(parent)>heap_size-1) return;
-                 ^
- 備考: in passing argument 1 of ‘std::ios_base& std::left(std::ios_base&)’
-   left(ios_base& __base)
-   ^~~~
-dijkstra.cpp:54:17: エラー: invalid initialization of reference of type ‘std::ios_base&’ from expression of type ‘int’
-  if (left(parent)==heap_size-1) {
-                 ^
-dijkstra.cpp:56:48: エラー: invalid initialization of reference of type ‘std::ios_base&’ from expression of type ‘int’
-    node_idx[node_data[parent].id] = left(parent);
-                                                ^
-dijkstra.cpp:59:25: エラー: invalid initialization of reference of type ‘std::ios_base&’ from expression of type ‘int’
-    down_heap(left(parent));
-                         ^
-In file included ･･････
-/usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/bits/ios_base.h:999:3: 備考: in passing argument 1 of ‘std::ios_base& std::left(std::ios_base&)’
-   left(ios_base& __base)
-   ^~~~
-dijkstra.cpp:62:28: エラー: invalid initialization of reference of type ‘std::ios_base&’ from expression of type ‘int’
-   if (node_data[left(parent)].cost<=node_data[right(parent)].cost) {
-                            ^
-In file included ･･････
-/usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/bits/ios_base.h:1007:3: 備考: in passing argument 1 of ‘std::ios_base& std::right(std::ios_base&)’
-   right(ios_base& __base)
-   ^~~~~
-dijkstra.cpp:63:52: エラー: invalid initialization of reference of type ‘std::ios_base&’ from expression of type ‘int’
-    if (node_data[parent].cost>node_data[left(parent)].cost) {
-                                                    ^
-dijkstra.cpp:65:35: エラー: invalid initialization of reference of type ‘std::ios_base&’ from expression of type ‘int’
-     node_idx[node_data[left(parent)].id] = parent;
-                                   ^
-In file included from /usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/ios:42:0,
-                 from /usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/ostream:38,
-                 from /usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/iostream:39,
-                 from dijkstra.cpp:1:
-/usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/bits/ios_base.h:999:3: 備考: in passing argument 1 of ‘std::ios_base& std::left(std::ios_base&)’
-   left(ios_base& __base)
-   ^~~~
-dijkstra.cpp:66:49: エラー: invalid initialization of reference of type ‘std::ios_base&’ from expression of type ‘int’
-     swap(node_data[parent],node_data[left(parent)]);
-                                                 ^
-dijkstra.cpp:74:27: エラー: invalid initialization of reference of type ‘std::ios_base&’ from expression of type ‘int’
-     down_heap(right(parent));
-                           ^
-In file included ･･････
-/usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/bits/ios_base.h:1007:3: 備考: in passing argument 1 of ‘std::ios_base& std::right(std::ios_base&)’
-   right(ios_base& __base)
-   ^~~~~
-dijkstra.cpp: 関数 ‘void push(int, int)’ 内:
-dijkstra.cpp:110:6: エラー: expected unqualified-id before ‘.’ token
-  node.push_back({id,cost});
-      ^
-dijkstra.cpp:110:26: エラー: expected primary-expression before ‘)’ token
-  node.push_back({id,cost});
-                          ^
-dijkstra.cpp: 関数 ‘void pop()’ 内:
-dijkstra.cpp:115:6: エラー: expected unqualified-id before ‘.’ token
-  node.pop_front();
-      ^
-dijkstra.cpp: 関数 ‘void change(int, int)’ 内:
-dijkstra.cpp:120:22: エラー: expected primary-expression before ‘.’ token
-  for (int i=0; i<node.size(); i++) {
-                      ^
-dijkstra.cpp:121:28: エラー: request for member ‘cost’ in ‘node_idx[i]’, which is of non-class type ‘int’
-   node_data[i]=node_idx[i].cost;
-                            ^~~~
 dijkstra.cpp: 関数 ‘void dijkstra()’ 内:
-dijkstra.cpp:129:3: エラー: ‘u’ was not declared in this scope
-   u[j]=9999;
-dijkstra.cpp:136:56: エラー: ‘class std::list<to_len>’ has no member named ‘len’; did you mean ‘cend’?
+dijkstra.cpp:151:66: エラー: no match for ‘operator[]’ (operand types are ‘int [30][30]’ and ‘std::_List_iterator<to_len>’)
-    if (vList[s].len+graph[s][j]<vList[j].len) vList[j].len=vList[s].len+graph[s][j];
+    if ((*it).len+graph[s][j]<(*it).len) (*it).len=(*it).len+graph[it][j];
-dijkstra.cpp:141:17: エラー: ‘class std::list<to_len>’ has no member named ‘len’; did you mean ‘cend’?
-    if (vList[j].len<minlen) {minlen=j; s=j;}
-                 ^~~
-                 cend
-dijkstra.cpp:147:1: エラー: a function-definition is not allowed here before ‘{’ token
- {
- ^
+                                                                  ^
-dijkstra.cpp:165:1: エラー: a function-definition is not allowed here before ‘{’ token
+dijkstra.cpp:156:40: エラー: no match for ‘operator=’ (operand types are ‘std::_List_iterator<to_len>’ and ‘int’)
- {
+    if ((*it).len<minlen) {minlen=j; it=j;}
- ^
+                                        ^
+In file included from /usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/list:63:0,
-dijkstra.cpp:170:1: エラー: 同上
+                 from dijkstra.cpp:3:
+/usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/bits/stl_list.h:128:12: 備考: candidate: constexpr std::_List_iterator<to_len>& std::_List_iterator<to_len>::operator=(const std::_List_iterator<to_len>&)
-dijkstra.cpp:181:1: エラー: 同上
+     struct _List_iterator
-dijkstra.cpp:191:1: エラー: 同上
+            ^~~~~~~~~~~~~~
+/usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/bits/stl_list.h:128:12: 備考: 第 1 引数を ‘int’ から ‘const std::_List_iterator<to_len>&’ へ変換する方法が不明です
+/usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/bits/stl_list.h:128:12: 備考: candidate: constexpr std::_List_iterator<to_len>& std::_List_iterator<to_len>::operator=(std::_List_iterator<to_len>&&)
- ^
+/usr/lib/gcc/i686-pc-cygwin/7.4.0/include/c++/bits/stl_list.h:128:12: 備考: 第 1 引数を ‘int’ から ‘std::_List_iterator<to_len>&&’ へ変換する方法が不明です
 ```
-※字数の関係上省略したところがあります。
 ### 該当のソースコード
 ```C++
@@ -304,6 +150,12 @@
 }
+int left(int i) {return 2*i+1;}
+int right(int i) {return 2*i+2;}
+void swap(node &a, node &b) {node tmp=a; a=b; b=tmp;}
 void down_heap(int parent)
@@ -426,7 +278,17 @@
 {
+	for (int i=0; i<N-1; i++) {
+		node_data[i].id=node_data[i+1].id;
+		node_data[i].cost=node_data[i+1].cost;
+	}
+	node_data[N-1].id=id;
-	node.push_back({id,cost});
+	node_data[N-1].cost=cost;
 }
@@ -436,7 +298,17 @@
 {
+	for (int i=0; i<N-1; i++) {
+		node_data[i].id=node_data[i+1].id;
+		node_data[i].cost=node_data[i+1].cost;
+	}
+	node_data[N-1].id=0;
-	node.pop_front();
+	node_data[N-1].cost=0;
 }
@@ -446,11 +318,7 @@
 {
-	for (int i=0; i<node.size(); i++) {
-		node_data[i]=node_idx[i].cost;
+	node_data[node_idx[id]].cost=cost;
-	}
 }
@@ -464,31 +332,37 @@
 	for (j=0; j<N; j++) {
+		for (auto it{vList[m].begin()}; it!=vList[m].end(); ++it) {
-		u[j]=9999;
+			path[j]=9999;
-		s=0;
+			s=0;
-		vList[s].len=0;
+			(*it).len=0;
+		}
+	}
-	for (m=1; m<N; m++) {
+	for (m=0; m<N; m++) {
 		path[s]=1;
-		for (j=0; j<N; j++) {
+		for (auto it{vList[m].begin()}; it!=vList[m].end(); ++it) {
 			if (graph[s][j]!=1) continue;
-			if (vList[s].len+graph[s][j]<vList[j].len) vList[j].len=vList[s].len+graph[s][j];
+			if ((*it).len+graph[s][j]<(*it).len) (*it).len=(*it).len+graph[it][j];
 		}
 		minlen=9999;
-		for (j=0; j<N; j++) {
+		for (auto it{vList[m].begin()}; it!=vList[m].end(); ++it) {
 			if (path[j]==1) continue;
-			if (vList[j].len<minlen) {minlen=j; s=j;}
+			if ((*it).len<minlen) {minlen=j; it=j;}
 		}
@@ -538,7 +412,15 @@
 {
+	path[0]=1;
+	for (auto next:graph[vertex]) {
+		if (path[next]==1) continue;
-	node.push(vertex);
+		rec_print_path(next);
+	}
 }
@@ -594,7 +476,7 @@
 ### 試したこと
-nodeの構造体があることに留意しidとcostに分けて考えるほか, ダイクストラ法はvListとnode_dataとの関係に留意ながら値を設定しました(主にC言語のダイクストラ法を参考にしました。)。
+イテレーターであるため, print_graph()を参考にdijkstra()を作成しました。rec_print_pathではfor(auto ...)を使って順に判定してみました。
 ### 補足情報（FW/ツールのバージョンなど）

字数の関係上エラーの文を省略したところがあるということを注釈で入れました。関数に_をつけました。

2021/11/14 16:21

投稿

wagashi_157

スコア51

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -4,9 +4,9 @@
 1. まず，３０個の頂点上のグラフを保持する二次元配列graph[N][N]，及び，その隣接リストvList[N]，更に，最短経路木を保持する一次元配列path[N] を（大域変数として）用意する．
-2. グラフG = (V,E) をランダムに生成する．（巻末の付録を参照．）そのグラフを出力する．（これらを関数gen graph(), print graph() で行う．）
+2. グラフG = (V,E) をランダムに生成する．（巻末の付録を参照．）そのグラフを出力する．（これらを関数gen_graph(), print_graph() で行う．）
-3. 優先度付きキューを初期化する．（これを関数init heap() で行う．）
+3. 優先度付きキューを初期化する．（これを関数init_heap() で行う．）
 4. 始点をs = 0，終点をt = 29 として，s からt への（G 上の）最短経路をダイクストラのアルゴリズムで探索する．（これを関数dijkstra() で行う．）
@@ -200,10 +200,10 @@
  ^
 ```
+※字数の関係上省略したところがあります。
 ### 該当のソースコード
 ```C++