週中トレーニングまとめ

最近見たのは最短回路の問題で、最短回路には4つの方法があり、異なる方法で適応条件と効率も異なる.最も簡単なのはfloyedアルゴリズムであり,三重サイクル遍歴であり,最外層が中間ノードを表すことに注意しなければならない.最もよく使われるのはDijkstraで、アルゴリズムは主に以下の考えです.

  :
 
1.               0,         ,      e[i][j],      ;
 
2.  ,              ,  dis[i],          dis[i]      。         i   ,      dis[i]=e[1][i];
 
3.  ,    ,       Q  , visit[i]=0  ;      P  , visit[i]=1  ;
 
4.     ,     , i  1...n-1,            i    ,       ;
 
5.                   i         ,  u;   u v    ;
 
6.  v      dis[v]>dis[u]+e[u][v],     dis[v]  ;
 
7.    ,           visit[i]=1;
 

その中で最も典型的な問題はhttps://blog.csdn.net/lanshan1111/article/details/82956405方西は双方向につながっていることに注意しなければならない.
まだ2つのアルゴリズムが典型的な問題を達成していないので、週末に補充します.感覚図論のこの部分は知識点が比較的に多くの関連性が比較的に大きくて、dfsのように、bfsのほとんどの問題はすべて使って、特に深さが優先的に検索して、とてもよく使うアルゴリズムで、毎回する問題のタイプはすべて異なって、しかし思想はすべて悪くて、パラメータは異なって、関数の適切なパラメータを設定します;また、枝を切る必要がある問題もあります.例えば、簡単な問題です.https://blog.csdn.net/lanshan1111/article/details/82944514ああ、また、パラメータを設定する深さ検索もあります.パラメータによって、やり方も違います.問題のようです.https://blog.csdn.net/lanshan1111/article/details/82942701
周末はまた一定の时間を割いて4つの常用最短アルゴリズムを見て、例題を見て、肝心なのはアルゴリズムの思想を徹底的に理解して、更にいくつかの検索問題をします.