- cmsg cancel <ncmmoq$ooq$2@dont-email.me> - 1 Update
- Dijkstra and Bellman-Ford-Moore's algorithms. - 1 Update
| bleachbot <bleachbot@httrack.com>: Mar 20 06:34PM +0100 |
| Ramine <ramine@1.1>: Mar 20 01:36PM -0700 Hello.... Dijkstra and Bellman-Ford-Moore's algorithms. I have just added 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. 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.1 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 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... 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 jtest1.dpr with a 32 bit delphi or freepascal compiler, but if you have compiled it with a 64 bit java compiler just compile after that jtest1.dpr with a 64 bit delphi or freepascal compiler. Please take a look at the jtest1.dpr example, you will notice that you have to call the java SP() method by passing it the name of the file that contains the graph and by passing it a second parameter that is the source from where you want to start searching and the third parameter is an array that contains the edges that you want to substract: i have enhanced the algorithm with a new option, 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. after that you have to call the java SP1() method by passing it the destination that you want to search, and the java SP1() method will return the shortest path to the destination and will return also the number of vertices. Please read carefully jtest1.dpr to learn more. This project consists also of this optimal implementation that uses Bellman-Ford-Moore's algorithm that takes a time complexity of E*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 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 compile1.bat batch file, after that if you have compiled it with a 32 bit java compiler just compile after that jtest2.dpr with a 32 bit delphi or freepascal compiler, but if you have compiled it with a 64 bit java compiler just compile after that jtest2.dpr with a 64 bit delphi or freepascal compiler. Please take a look at the jtest2.dpr example, you will notice that you have to call the java SP() method by passing it the name of the file that contains the graph and by passing it a second parameter that is the source from where you want to start searching and the third parameter is an array that contains the edges that you want to substract: i have enhanced the algorithm with a new option, 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. after that you have to call the java SP1() method by passing it the destination that you want to search, and the java SP1() method will return the shortest path to the destination and will return also the number of vertices. Please read carefully jtest2.dpr to learn more, that's all. You 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. |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.programming.threads+unsubscribe@googlegroups.com. |
No comments:
Post a Comment