優先度付きキューを利用したダイクストラ法のアルゴリズムのプログラムを作成したいです。

Question

前提・実現したいこと

以下の要領を基に優先度付きキューを適切に利用したダイクストラ法のアルゴリズムを実装しようと思っています。

1. まず，３０個の頂点上のグラフを保持する二次元配列graph[N][N]，及び，その隣接リストvList[N]，更に，最短経路木を保持する一次元配列path[N] を（大域変数として）用意する．
2. グラフG = (V,E) をランダムに生成する．（巻末の付録を参照．）そのグラフを出力する．（これらを関数gen_graph(), print_graph() で行う．）
3. 優先度付きキューを初期化する．（これを関数init_heap() で行う．）
4. 始点をs = 0，終点をt = 29 として，s からt への（G 上の）最短経路をダイクストラのアルゴリズムで探索する．（これを関数dijkstra() で行う．）
5. 到達可能であればpath が示す経路を「始点から順に」出力する．（配列pathは，終点から辿っていかざるをえず，それを順に表示すると逆順になってしまう！スタックか再帰を用いると解決できる．）到達不可能であればその旨を出力する．（グラフはランダム生成なためそういう場合もある．）

発生している問題・エラーメッセージ

push,pop,changeのプログラムは解決できましたが, 到達可能を判定するためのrec_print_pathの表現の仕方が分からず困っています(print_pathにもあるようにvoid関数で実装したいです)。それとlist関数を使ってdijkstra()を実装したいのですが, イテレータで表現してもエラーが出てしまい, 原因が分かりません。イテレーターに慣れていないのとダイクストラ法で図は描けるもののプログラムとなると中々上手くいかないので教えてほしいです。

dijkstra.cpp: 関数 ‘void dijkstra()’ 内:
dijkstra.cpp:151:66: エラー: no match for ‘operator[]’ (operand types are ‘int [30][30]’ and ‘std::_List_iterator<to_len>’)
    if ((*it).len+graph[s][j]<(*it).len) (*it).len=(*it).len+graph[it][j];
                                                                  ^
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,
                 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>&)
     struct _List_iterator
            ^~~~~~~~~~~~~~
/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>&&’ へ変換する方法が不明です

該当のソースコード

#include<iostream>
#include<random>
using namespace std;

#define N		30
#define DENSITY		9
#define MAX_COST	100

struct node {
	int id;
	int cost;
};
struct to_len {
        int to, len;
};
list<to_len> vList[N];

node node_data[N];
int node_idx[N];
int heap_size;

void gen_node_data()
{
	mt19937 mt{random_device{}()};
	uniform_int_distribution<int> dist(0,MAX_COST);
	heap_size = 0;

	for (int i=0; i<N; i++) {
		node_data[i].id = i;
		node_data[i].cost = dist(mt);
		heap_size++;

		node_idx[i] = i;
	}
}

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 up_heap(int child)
{
	int parent=(child-1)/2;
	if (child>heap_size-1) return;

	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]);
			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)]);
				up_heap(parent);
			}
		} else {
			if (node_data[right(parent)].cost>node_data[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)]);
				up_heap(parent);
			}
		}
	}
}
void make_heap()
{
	for (int i=(N-1)/2; i>=0; i--) {
		down_heap(i);
	}
}
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 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)
{
	int old;
	old=node_data[node_idx[id]].cost;
	node_data[node_idx[id]].cost=cost;
	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_graph();
	print_graph();

	init_heap();
	dijkstra();

	print_path();

	return 0;
}

試したこと

イテレーターであるため, print_graph()を参考にdijkstra()を作成しました。rec_print_pathではfor(auto ...)を使って順に判定してみました。

補足情報（FW/ツールのバージョンなど）

C++17を利用しています。

Comments

[Zuishin]

C++ でこんな機械的に回答できるものに何の反応もないなんて何をしたんだろうと思って質問一覧を見たら、見るからに課題の丸投げを連発してる人だった。
無理な課題ならやらなくていいのでは？

[actorbug]

まずは、以前のソースからleft,right関数の定義をコピペして、dijkstra関数の閉じカッコが足りないのを直しましょう。
あとは、コピペするなとは言いませんが、せめて内容を説明できるぐらいに理解してからにしましょう。
push関数で、どのような処理が必要なのか、日本語で説明できますか?
できないようなら、「ヒープ 追加」などで検索して、どういう原理で動作するのか理解しましょう。

[actorbug]

正直、push,pop,changeすべて間違っています。(ついでにいうとup_heapも)
changeはコードが足りない程度ですが、push,popはやろうとしていること自体が間違っています。
まずは、優先度付きキュー単独で正しく動作するところまで作りこむことをお勧めします。
削除依頼の出ている一つ前の質問のコードがまともに動作するまで、dijkstraには手を出さない方がよいでしょう。

[wagashi_157]

push,popはstackやqueueだとそのまま入力すれば実装できますが, int型配列だとどのように表現すれば良いかを考えたときにインターネットで調べたことも含め「値の更新を行う」ことしか思いつきませんでした。
優先度付きキューだとアップヒープも含めプログラムのどこに違いがあるのかを教えてほしいです。

[actorbug]

なぜ間違っていなかったdown_heapを消して、make_heapを誤ったものに書き換えてしまったのでしょうか。
あと、インターネットで調べて「思いついた」内容を実装するのではなく、インターネットで正しいやり方を調べて、それを実装してください。
このページのP21以降の説明と疑似コードなど参考にならないでしょうか。
http://www.sd.is.uec.ac.jp/koga/lecture/FSkiso1/kiso1_04.pdf

Answer 1

ダイクストラ法のwebサイトを参考にしたら何とかできました。