深さ優先探索で各地点への最短路を求めるプログラムについて

Question

この問題を解いていたのですが、解説を見て少し分からないところがありました

解説には、深さ優先探索を使って、Kから各地点への最短路を前計算する、とありますが、そこのサンプルコードが良くわかりません

void dfs(ll v,ll p,ll d){
	depth[v]=d;
	for(auto &e : tree[v]){
		if(e.to==p)continue;
		dfs(e.to,v,d+e.cost);
	}

}

...


dfs(k,-1,0);

やっていることとしては、移動できる地点へ移動してコストを足していく、前の地点と移動したい地点が同じならcontinue、ということで目的地までの経路が求まるのは分かるのですが、どうしてこれで「最短経路」が求まるのでしょうか
感覚的には初めのdepthのところで、depth[v]=min(depth[v],d);という風になるように感じます
後から計算した数値の方が高い値になることはないのでしょうか

どなたか分かる方よろしくお願いします

Answer 1

2つポイントがあります。

1. 閉路のないグラフであること
2. if(e.to==p)continue; つまり、「もどらない」こと

1の条件より行った道を戻らなければ、複数回同じ頂点にたどり着くことはありません。
そして2の条件から戻ることをしません。

よって、同じ頂点には複数回たどり着かないので問題なく最短距離が得られます

Comments

[asm]

ダイキストラ法の解説でよくあるやつだけど、

ひもで木構造作って、必ず通る点Kをつまんで持ち上げた場合の
点xまでの距離と点yまでの距離の合計が答えになると思うとよいかも

[l_h_l_h]

回答ありがとうございます
閉路がないことを見落としていました
ありがとうございました！