Groups | Search | Server Info | Login | Register

Groups > comp.programming > #7865

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

Show all headers | View raw

On 6/20/2017 12:41 PM, rami18 wrote:
> 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: aminer@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:

I mean arguments, not argements.

> 
> 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.

Back to comp.programming | Previous | Next | Find similar

Thread

Re: Dijkstra and Bellman-Ford-Moore's algorithms were updated to version 1.2 rami18 <coco@coco.com> - 2017-06-20 13:23 -0400

csiph-web