はじめに
みなさん、こんにちは。このトピックは、Dijkstaアルゴリズムが影響を受けた最小コストの最大フローに関するこの記事の論理的な続きとして書いています。 アルゴリズムの説明とさまざまな実装は問題なく見つけることができ、「ホイール」を発明しないことは著者に同意しますが、それでもここでC＃での実用的な実装を説明します。 ちなみに、私はLINQを使用しているため、NET 3.5が動作する必要があります。
UPD最後にコードをクリーンアップしました:)
理論のビット
彼らがすぐに私の庭に石を投げないように、Wikipediaのような目立たないリソースに関するアルゴリズムの非常に良い説明へのリンクを提供します:)。 アルゴリズムは非常によく説明されているので、例を見ることを特にお勧めします。 そこから素材をコピーするのは無意味です。 すべて、理論が研究されたと考えます。
開始する
このコードは、重み付けされた無向グラフでのアルゴリズムの実装を表します。 このアルゴリズムの実装を検討してください。
このアルゴリズムのオブジェクトは3つのクラスです。
•Apoint-グラフの上部を実装するクラス
•Rebro-グラフエッジを実装するクラス
•DekstraAlgoritm-ダイクストラのアルゴリズムを実装するクラス。
これらのクラスと最も重要なメソッドを詳しく見てみましょう。
アオイン
このクラスには5つのフィールドが含まれます。
•public float ValueMetka {get; セット; }このフィールドは、この頂点のラベル値を格納します。 プログラムでは、99999など、非常に大きな数が無限大で取得されます。
•パブリックストリング名{get; セット; }はラベルの名前です。 このフィールドは、読み取り可能な結果を得るためにのみ必要です。
•public bool IsChecked {get; セット; }-ラベルがマークされているかどうかを意味します
•public APoint predPoint {get; セット; }-ポイントの「祖先」、つまり 最短ルートの電流の祖先であるポイント。
•パブリックオブジェクトSomeObj {get; セット; }-オブジェクト
このクラスには重要なメソッドは含まれていません。
レブロ
このクラスには3つのフィールドが含まれます。
•public APoint FirstPoint {get; セット; }-エッジの初期頂点
•public APoint SecondPoint {get; セット; }-エッジの終了頂点
•public float Value {get; セット; }は重み係数です。
このクラスには重要なメソッドは含まれていません。
デクストラ・アルゴリム
このクラスは、ダイクストラのアルゴリズムのグラフおよび実装です。 2つのフィールドが含まれます。
•public APoint []ポイント{取得; セット; }-頂点の配列
•public Rebro [] rebra {get; セット; }-エッジの配列
したがって、これらの2つの配列はグラフを反映しています。 メソッドを検討してください：
•プライベートAPoint GetAnotherUncheckedPoint（）
このメソッドは、アルゴリズムに従って、最も削除されていない次のマークされていない頂点を返します。
•public void OneStep（APoint開始ポイント）
このメソッドは、特定のポイントに対してアルゴリズムの1ステップを実行します。
•プライベートIEnumerable Pred（APoint currpoint）
このメソッドは、指定されたポイントの近傍を検索し、ポイントのコレクションを返します。
•パブリックストリングMinPath（APoint開始、APoint終了）
このメソッドは、アルゴリズムで見つかった開始点から終了点までの最短パスを返します。 このメソッドは、パスを視覚化するために使用されます。
•public void AlgoritmRun（APoint beginp）
このメソッドはアルゴリズムを開始し、開始点を入力として受け取ります。
主な方法はすべて説明されていますが、図1にアルゴリズムのプロセス全体を示します。 主なOneStepメソッドを図2に示します。
図1 アルゴリズム全体の操作
図2。 OneStepメソッドの操作
コード
最後に、コード自体を検討します。 各クラスで彼は詳細なコメントを書いた。
/// <summary>
/// .
/// </summary>
class DekstraAlgorim
{
public Point[] points { get ; private set ; }
public Rebro[] rebra { get ; private set ; }
public Point BeginPoint { get ; private set ; }
public DekstraAlgorim(Point[] pointsOfgrath, Rebro[] rebraOfgrath)
{
points = pointsOfgrath;
rebra = rebraOfgrath;
}
/// <summary>
///
/// </summary>
/// <param name="beginp"></param>
public void AlgoritmRun(Point beginp)
{
if ( this .points.Count() == 0 || this .rebra.Count() == 0)
{
throw new DekstraException( " !" );
}
else
{
BeginPoint = beginp;
OneStep(beginp);
foreach (Point point in points)
{
Point anotherP = GetAnotherUncheckedPoint();
if (anotherP != null )
{
OneStep(anotherP);
}
else
{
break ;
}
}
}
}
/// <summary>
/// , .
/// </summary>
/// <param name="beginpoint"></param>
public void OneStep(Point beginpoint)
{
foreach (Point nextp in Pred(beginpoint))
{
if (nextp.IsChecked == false ) //
{
float newmetka = beginpoint.ValueMetka + GetMyRebro(nextp, beginpoint).Weight;
if (nextp.ValueMetka > newmetka)
{
nextp.ValueMetka = newmetka;
nextp.predPoint = beginpoint;
}
else
{
}
}
}
beginpoint.IsChecked = true ; //
}
/// <summary>
/// . .
/// </summary>
/// <param name="currpoint"></param>
/// <returns></returns>
private IEnumerable <Point> Pred(Point currpoint)
{
IEnumerable <Point> firstpoints = from ff in rebra where ff.FirstPoint==currpoint select ff.SecondPoint;
IEnumerable <Point> secondpoints = from sp in rebra where sp.SecondPoint == currpoint select sp.FirstPoint;
IEnumerable <Point> totalpoints = firstpoints.Concat<Point>(secondpoints);
return totalpoints;
}
/// <summary>
/// , 2
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
private Rebro GetMyRebro(Point a, Point b)
{ // 2
IEnumerable <Rebro> myr = from reb in rebra where (reb.FirstPoint == a & reb.SecondPoint == b) || (reb.SecondPoint == a & reb.FirstPoint == b) select reb;
if (myr.Count() > 1 || myr.Count() == 0)
{
throw new DekstraException( " !" );
}
else
{
return myr.First();
}
}
/// <summary>
/// , "" .
/// </summary>
/// <returns></returns>
private Point GetAnotherUncheckedPoint()
{
IEnumerable <Point> pointsuncheck = from p in points where p.IsChecked == false select p;
if (pointsuncheck.Count() != 0)
{
float minVal = pointsuncheck.First().ValueMetka;
Point minPoint = pointsuncheck.First();
foreach (Point p in pointsuncheck)
{
if (p.ValueMetka < minVal)
{
minVal = p.ValueMetka;
minPoint = p;
}
}
return minPoint;
}
else
{
return null ;
}
}
public List <Point> MinPath1(Point end)
{
List <Point> listOfpoints = new List <Point>();
Point tempp = new Point();
tempp = end;
while (tempp != this .BeginPoint)
{
listOfpoints.Add(tempp);
tempp = tempp.predPoint;
}
return listOfpoints;
}
* This source code was highlighted with Source Code Highlighter .
/// <summary>
/// ,
/// </summary>
class Rebro
{
public Point FirstPoint { get ; private set ; }
public Point SecondPoint { get ; private set ; }
public float Weight { get ; private set ; }
public Rebro(Point first, Point second, float valueOfWeight)
{
FirstPoint = first;
SecondPoint = second;
Weight = valueOfWeight;
}
}
* This source code was highlighted with Source Code Highlighter .
/// <summary>
/// ,
/// </summary>
class Point
{
public float ValueMetka { get ; set ; }
public string Name { get ; private set ; }
public bool IsChecked { get ; set ; }
public Point predPoint { get ; set ; }
public object SomeObj { get ; set ; }
public Point( int value , bool ischecked)
{
ValueMetka = value ;
IsChecked = ischecked;
predPoint = new Point();
}
public Point( int value , bool ischecked, string name)
{
ValueMetka = value ;
IsChecked = ischecked;
Name = name;
predPoint = new Point();
}
public Point()
{
}
}
* This source code was highlighted with Source Code Highlighter .
// <summary>
///
/// </summary>
static class PrintGrath
{
public static List < string > PrintAllPoints(DekstraAlgorim da)
{
List < string > retListOfPoints = new List < string >();
foreach (Point p in da.points)
{
retListOfPoints.Add( string .Format( "point name={0}, point value={1}, predok={2}" , p.Name, p.ValueMetka, p.predPoint.Name ?? " " ));
}
return retListOfPoints;
}
public static List < string > PrintAllMinPaths(DekstraAlgorim da)
{
List < string > retListOfPointsAndPaths = new List < string >();
foreach (Point p in da.points)
{
if (p != da.BeginPoint)
{
string s = string .Empty;
foreach (Point p1 in da.MinPath1(p))
{
s += string .Format( "{0} " , p1.Name);
}
retListOfPointsAndPaths.Add( string .Format( "Point ={0},MinPath from {1} = {2}" , p.Name, da.BeginPoint.Name, s));
}
}
return retListOfPointsAndPaths;
}
}
* This source code was highlighted with Source Code Highlighter .
class DekstraException:ApplicationException
{
public DekstraException( string message): base (message)
{
}
}
* This source code was highlighted with Source Code Highlighter .
作業結果
理論で説明されているグラフのアルゴリズムの例を次に示します。
ポイント名= 1、ポイント値= 0、predok =祖先なし
ポイント名= 2、ポイント値= 9999、predok =祖先なし
ポイント名= 3、ポイント値= 9999、predok =祖先なし
ポイント名= 4、ポイント値= 9999、predok =祖先なし
ポイント名= 5、ポイント値= 9999、predok =祖先なし
ポイント名= 6、ポイント値= 9999、predok =祖先なし
============
ポイント名= 1、ポイント値= 0、predok =祖先なし
ポイント名= 2、ポイント値= 7、predok = 1
ポイント名= 3、ポイント値= 9、predok = 1
ポイント名= 4、ポイント値= 20、predok = 3
ポイント名= 5、ポイント値= 20、predok = 6
ポイント名= 6、ポイント値= 11、predok = 3
最短経路
ポイント= 2、1からのMinPath = 2
ポイント= 3、1からのMinPath = 3
ポイント= 4、1からのMinPath = 4 3
ポイント= 5、1からのMinPath = 5 6 3
ポイント= 6、1からのMinPath = 6 3
おわりに
特にキックしないでください、私の1つの記事:)コメントを歓迎します！ 誰かがコードを必要としていると思います。