向上編-最短経路問題(図論)-『アルゴリズムノート』同期ノートの総括と補充

テーマのポイント:

負のループを持たない単一ソース最短パス

Dijkstra(dfsに合わせて優先キュー最適化)

一般的な単一ソース最短パス

Dijkstra

Bellman-Ford

SPFA

フルソース最短パス

Floyd

暴力:頂点ごとにDijkstra

を1回行う

解ける質問:

基礎問題(第1ルーラー):最短パス

引用問題(第2スケール):辺権費用配列c[],点権資源配列w[],最短パス数num[],経路上のノード数pt[],前駆ノード記録pre[];

基礎問題(最短経路を求める)は第1のルーラーであり、残りの引申問題は第2のルーラーである.最短経路を求めるにはDijkstraアルゴリズムを使用し、過程でpre[]ストレージを使用し、dfsはpre[]を検索して第2のルーラー問題を解決する.PS:第2のルーラーは複雑な計算に関わると、実は模擬問題である

全网最完!PAT甲組1003.Emergency(優先キュー実装ディジェストラアルゴリズム、Bellmanアルゴリズム、SPFA)の考え方と注意点–「アルゴリズムノート」

を補足

PAT甲組1072.Gas Stationの考え方と注意点–「アルゴリズムノート」

を補充する

PAT甲組1018.Public Bike Managementの考え方と注意点–アルゴリズムノート

を追加

PAT甲組1111.Online Map構想解析とコード

プログラミングはいつも無視する問題です

Dijkstra最外層サイクルN回(Nは頂点数)の意味:すべての頂点にアクセスし、サイクル中にvis[]でマークするために、サイクル内で再実行し、最短エッジを見つけ、最短パスを更新する操作.

dfs逆遍歴、逆出力:pre[]dfsの場合、再帰的な性質が逆遍歴であるため、リーフノード(境界)がソース点であり、境界が経路点に対する重みを計算する際に、vectortempPath

に逆順序でアクセスすることを忘れないでください.

dfsは依然としてプロセス中に特有の逆方向動作

を覚えておく必要がある.

tempPath.push_back(v);
……
tempPath.pop_back();

dfsは完全なパスを得た後の計算問題を得た:前提:境界に着いた後、手動で境界ノードpush_をbackが現在のパスに到達すると、完全なパスが得られます.その後、パス全体を逆順序で巡回します.

ポイント重みの計算:パス内のすべてのポイントを巡回すると

になります.

計算辺権:経路中の点とその点の後続を遍歴し、2つの端点を取得すると辺権を得る

計算を行う.

隣接行列にアクセスし、Dijkstraは現在の頂点に接続された点にアクセスする:エッジにif(!vis[v]&&G[u][v])が存在するかどうかを先に判断しなければならない.そうしないと、あるエッジが存在しない(G[u][v]==0)最短距離

を誤って更新する

隣接テーブルにアクセスすると、vectorパスのループ変数iの意味:iは別の頂点を表すものではなく、別の頂点はvector[i]に格納され、iはループ変数であり、頂点値の取得を補助する役割

である.

平均値を計算する方法:2つの方法は、1つは循環しながら平均値を求めるのではなく、循環して加算してから平均値を求めるのですが、問題をするときに点があったら循環しながら平均値を求めるのが第一選択でしょうか?現在も疑問視されている

前駆ノードセットpre[]:現在のノードの前駆pushを入れ、vは現在のノード、uはvの前駆ノードであり、

を明確に区別する.

for(int v = 0; v < G[u].size(); ++i)
{
	if(    )
	pre[v].push_back(u);
}

次の点に注意してください.

具体的な経路を得るには、pre[]とdfs(再帰)思想を通じて、逆アクセス(すなわち、終点アクセスから起点へ)であることに注意しなければならない.この方法が最も安全である(Dijkstra、Bellman、SPFAの場合)

単一Dijkstra:

テーマの要求に基づいて辺権費用配列c[]を増減し、点権資源配列w[]をクリックし、最短パス数num[]をクリックし、パス上のノード数pt[]をクリックし、前駆ノード記録pre[]をクリックします.

各データ構造の初期化問題

に注意する.

Dijkstra+dfs:第2スケールの優先順位を解く

前提:前駆ノード集合vectorpre[maxn]を宣言し、dfs

を行うことができる.

アクセスパス中にtempPathでパス中のノード(逆記録)

を記録する.

フルパス計算tempValueと最適値optValueとの比較を増やし、最適値が存在するtempPathを最適パスoptPathに

格納する

再帰アクセス時に逆記録される(tempPath.size(-1は起点)ため、ポイント重みエッジ権を計算する際にfor(int i=tempPath.size()-1に逆記述アクセスすることが望ましい.i >= 0; i–)

全源最短経路:Floyedと暴力Dijkstraと比較して,時間的複雑度はいずれもO(N 3)であるが計算量は異なる.

効果比較

Dijkstraの過程で多くの経路と結果の計算は重複しており、時間の複雑さは同じであるが、演算量の差は多い.

Dijkstraはより多くの空間的複雑さを必要とし、Floydは隣接行列や隣接テーブルを必要とせず、vis[]配列