Discussion:
Dijkstra and Bellman-Ford-Moore's algorithms were updated to version 1.2
(trop ancien pour répondre)
rami18
2017-06-20 16:40:29 UTC
Permalink
Raw Message
Hello......


Dijkstra and Bellman-Ford-Moore's algorithms were updated to version 1.2


Dijkstra and Bellman-Ford-Moore's algorithms
Dijkstra's algorithm for Delphi and FreePascal. Computes the shortest
path tree. Assumes all weights are nonnegative.

and

Bellman-Ford-Moore's algorithm for Delphi and FreePascal, computes the
shortest path tree. The edge weights can be positive, negative or zero.


Version: 1.2


Authors: Robert Sedgewick, Kevin Wayne
and enhanced by Amine Moulay Ramdane

Email: ***@videotron.ca

Description:

This project consists of this optimal implementation that uses
Dijkstra's algorithm with a binary heap that takes a time complexity of
E*log(V), V is the number of vertices and E is the number of edges. This
library can be used in parallel clusters manner by dividing your graph
in many parts to speed much your parallel algorithm, also i have added
an option to the algorithm that permits you to pass the edges of the
graph that you can substract from your graph to be able to give you
algorithm more control if you want for example to ignore congestions in
some roads...

You have to have a 32 bit or 64 bit java compiler and you have to
compile first the java library by running the compile1.bat batch file,
after that if you have compiled it with a 32 bit java compiler just
compile after that test1.pas with a 32 bit delphi or freepascal
compiler, but if you have compiled it with a 64 bit java compiler just
compile after that test1.pas with a 64 bit delphi or freepascal compiler.

This project also consists also of this optimal implementation that uses
Bellman-Ford-Moore's algorithm that takes a time complexity of V*E, V is
the number of vertices and E is the number of edges. This library can be
used in parallel clusters manner by dividing your graph in many parts to
speed much your parallel algorithm, also i have added an option to the
algorithm that permit you to pass the edges of the graph that you can
substract from your graph to be able to give you algorithm more control
if you want for example to ignore congestions in some roads...

The Bellman-Ford-Moore (BFM) algorithm which predates Dijkstra by 4 or 5
years. Better still, BFM is robust in the sense that it can handle
negative arc-weights and detect and find negative cycles. Dijkstra
cannot do this.

You have to have a 32 bit or 64 bit java compiler and you have to
compile first the java library by running the compile2.bat batch file,
after that if you have compiled it with a 32 bit java compiler just
compile after that test2.pas with a 32 bit delphi or freepascal
compiler, but if you have compiled it with a 64 bit java compiler just
compile after that test2.pas with a 64 bit delphi or freepascal compiler.

You have two procedures to call, here they are:

procedure solveDijkstra(filename:string;source:integer;
destination:integer;edgesToSustract:arr3;var edges:TDijkstraInfo;var
totalNumberOfVertices:integer;var distanceShortestPath:system.double);

procedure solveBellmanFord(filename:string;source:integer;
destination:integer;edgesToSustract:arr3;var edges:TDijkstraInfo;var
totalNumberOfVertices:integer;var distanceShortestPath:system.double);

The argements are the same, here they are:

Filename: is the filename to pass, the filename is organized as:

You write the number of vertices in the first line, and after that you
write the number of edges in the second line and after that you write
the edge and its weight in the each line.

source: is the source vertex.

destination: is the destination vertex.

edgesToSustract: is the edges to substract from the graph,
you can pass the edges that you want to substract by passing the edges
in an array, the edges must be arranged two by two in the array, the
first and the second element of the array is the first edge that you
want to substract etc., i have enhanced the algorithm with this new option.

totalNumberOfVertices: is the returned total number of vertices of the
graph.

distanceShortestPath: is the returned shortest path distance.

Have fun with it !

You can download it from:

https://sites.google.com/site/aminer68/dijkstra-and-bellman-ford-moore-s-algorithms

Language: FPC Pascal v2.2.0+ / Delphi 7+: http://www.freepascal.org/

Operating Systems: Windows,

Required FPC switches: -O3 -Sd -dFPC -dFreePascal

-Sd for delphi mode....

Required Delphi switches: -$H+ -DDelphi

For Delphi XE-XE7 use the -DXE switch



Thank you,
Amine Moulay Ramdane.
rami18
2017-06-20 17:23:24 UTC
Permalink
Raw Message
Post by rami18
Hello......
Dijkstra and Bellman-Ford-Moore's algorithms were updated to version 1.2
Dijkstra and Bellman-Ford-Moore's algorithms
Dijkstra's algorithm for Delphi and FreePascal. Computes the shortest
path tree. Assumes all weights are nonnegative.
and
Bellman-Ford-Moore's algorithm for Delphi and FreePascal, computes the
shortest path tree. The edge weights can be positive, negative or zero.
Version: 1.2
Authors: Robert Sedgewick, Kevin Wayne
and enhanced by Amine Moulay Ramdane
This project consists of this optimal implementation that uses
Dijkstra's algorithm with a binary heap that takes a time complexity of
E*log(V), V is the number of vertices and E is the number of edges. This
library can be used in parallel clusters manner by dividing your graph
in many parts to speed much your parallel algorithm, also i have added
an option to the algorithm that permits you to pass the edges of the
graph that you can substract from your graph to be able to give you
algorithm more control if you want for example to ignore congestions in
some roads...
You have to have a 32 bit or 64 bit java compiler and you have to
compile first the java library by running the compile1.bat batch file,
after that if you have compiled it with a 32 bit java compiler just
compile after that test1.pas with a 32 bit delphi or freepascal
compiler, but if you have compiled it with a 64 bit java compiler just
compile after that test1.pas with a 64 bit delphi or freepascal compiler.
This project also consists also of this optimal implementation that uses
Bellman-Ford-Moore's algorithm that takes a time complexity of V*E, V is
the number of vertices and E is the number of edges. This library can be
used in parallel clusters manner by dividing your graph in many parts to
speed much your parallel algorithm, also i have added an option to the
algorithm that permit you to pass the edges of the graph that you can
substract from your graph to be able to give you algorithm more control
if you want for example to ignore congestions in some roads...
The Bellman-Ford-Moore (BFM) algorithm which predates Dijkstra by 4 or 5
years. Better still, BFM is robust in the sense that it can handle
negative arc-weights and detect and find negative cycles. Dijkstra
cannot do this.
You have to have a 32 bit or 64 bit java compiler and you have to
compile first the java library by running the compile2.bat batch file,
after that if you have compiled it with a 32 bit java compiler just
compile after that test2.pas with a 32 bit delphi or freepascal
compiler, but if you have compiled it with a 64 bit java compiler just
compile after that test2.pas with a 64 bit delphi or freepascal compiler.
procedure solveDijkstra(filename:string;source:integer;
destination:integer;edgesToSustract:arr3;var edges:TDijkstraInfo;var
totalNumberOfVertices:integer;var distanceShortestPath:system.double);
procedure solveBellmanFord(filename:string;source:integer;
destination:integer;edgesToSustract:arr3;var edges:TDijkstraInfo;var
totalNumberOfVertices:integer;var distanceShortestPath:system.double);
I mean arguments, not argements.
Post by rami18
You write the number of vertices in the first line, and after that you
write the number of edges in the second line and after that you write
the edge and its weight in the each line.
source: is the source vertex.
destination: is the destination vertex.
edgesToSustract: is the edges to substract from the graph,
you can pass the edges that you want to substract by passing the edges
in an array, the edges must be arranged two by two in the array, the
first and the second element of the array is the first edge that you
want to substract etc., i have enhanced the algorithm with this new option.
totalNumberOfVertices: is the returned total number of vertices of the
graph.
distanceShortestPath: is the returned shortest path distance.
Have fun with it !
https://sites.google.com/site/aminer68/dijkstra-and-bellman-ford-moore-s-algorithms
Language: FPC Pascal v2.2.0+ / Delphi 7+: http://www.freepascal.org/
Operating Systems: Windows,
Required FPC switches: -O3 -Sd -dFPC -dFreePascal
-Sd for delphi mode....
Required Delphi switches: -$H+ -DDelphi
For Delphi XE-XE7 use the -DXE switch
Thank you,
Amine Moulay Ramdane.
Loading...