rybufc icon

Diikstra

rybufc | PRO | 02/04/18 12:03:05 PM UTC | 0 ⭐ | 7385 👁️ | Never ⏰ | []
Pascal |

2.65 KB

|

None

|

0 👍

/

0 👎

?uses System.Collections.Generic;
 
const
  MaxN = 1000;
 
type
  Point = class
  
  private 
    _index: integer;
    _previous: Point;
    _value: integer
  
  public 
    constructor(index: integer);
    begin
      _index := index;
      _previous := nil;
    end;
    
    procedure SetPrevious(previous: Point);
    procedure SetValue(value: integer);
    function ToString(): string;
    property Value: integer read _value;
    property Index: integer read _index;
    property Previous: Point read _previous;
  end;
 
function Point.ToString(): string;
begin
  if (not (previous = nil)) then
    result := 'index: ' + _index + #10 + 'value ' + _value + ' ;' + #10 
      + 'previous: ' + previous.ToString()
  else
    result := 'index: ' + _index + #10 + 'value ' + _index;
end;
 
procedure Point.SetPrevious(previous: Point);
begin
  _previous := previous;
end;
 
procedure Point.SetValue(value: integer);
begin
  _value := value;
end;
 
function Diikstra(startPoint: integer;
              params graph: Array[,] of integer): Array of Point;
begin
  var queue: Queue<Point>;
  queue := new Queue<Point>;
  
  var calculatedGraph: Array of Point;
  calculatedGraph := new Point[Length(graph, 0)];
  for var i := 0 to Length(calculatedGraph, 0) - 1 do
  begin
    var temp: Point;
    temp := new Point(i);
    temp.SetValue(integer.MaxValue);
    calculatedGraph[i] := temp;
  end;
  
  calculatedGraph[startPoint].SetValue(0);
  
  var visited: Array[0..MaxN] of boolean;  
  queue.Enqueue(calculatedGraph[startPoint]);
  
  while queue.Count <> 0 do
  begin
    var current: Point;
    current := queue.Dequeue();
    visited[current.Index] := true;
    
    for var i := 0 to Length(graph, 1) - 1 do
    begin
      if (graph[current.Index, i] > 0) and (not visited[i]) then
      begin
        if(calculatedGraph[i].Value > 
          current.Value + graph[current.Index, i]) then
          begin
            calculatedGraph[i].SetValue(current.Value + graph[current.Index, i]);
            calculatedGraph[i].SetPrevious(current);
          end;
        queue.Enqueue(calculatedGraph[i]);
      end;
    end;
  end;
  result := calculatedGraph;
end;
 
begin
  var graph: array[,] of integer;
  graph := new integer[10, 10];
  for var i := 0 to Length(graph, 0) - 1 do
    for var j := 0 to Length(graph, 1) - 1 do
      graph[i, j] := 0;
  var startPoint, targetPoint: integer;
  
  startPoint := 0;  
  graph[0, 3] := 1;
  graph[3, 5] := 1;
  graph[0, 5] := 10;
  var calculatedGraph: Array of Point;
  calculatedGraph := Diikstra(startPoint, graph);
  Writeln(calculatedGraph[5].ToString());
end.

Comments

  •  icon
    01/01/70 12:00:00 AM UTC
    Plain Text |

    0 B

    |

    👍

    /

    👎

    
        
  •  icon
    01/01/70 12:00:00 AM UTC
    Plain Text |

    0 B

    |

    👍

    /

    👎