Dijkstra Algorithm

Standard

I started to implement routing algorithms and I began with the easiest one first: Dijkstra.
It’s a kind of greedy algorithm which calculates a shortest path from one node to another one in a graph.
The edges of the graph can have weights – if no weights are needed then assume 1 as the weight of each edge.
You need a priority queue in order to work through the graph and find the shortest path.
When using Fibonacci Heaps for implementing the priority queue then the runtime complexity is O(n * log(n) + m).

 

Enterprise Architect “GetAllLatest” Workaround

Standard

Since I’m working in a highly distributed engineering team (with SVN as the repository for the EA model) it is necessary to update the EA model quite often. Since the “GetAllLastest” provided by EA updates the complete model – which takes hours – I created a short script that updates only the branch of the model which is selected in the Project Browser. Feel free to use it and leave comments about it.

To install it follow this:

Step 1 “Install Script”

    • Go to “Tools –>Scripting” (the script window opens)
    • Create a new “Project Browser Script Group” (call it whatever you like i.e. “My Model Update”)
    • Then create a new VBScript (again call it whatever you like i.e. “Update Selected”)
    • Double click the new script entry and copy & paste the code from below

Step 2 “Run Script”

    • Select the package in the project browser you want to update
    • Click on the “Run Script” button in the script window
    • Or right-click on the package in the Project Browser –> “Scripts” menu

 

Fibonacci Heap

Standard

I needed a priority queue for my routing algorithm. And therefore I implemented this Fibonacci Heap data structure. It works pretty well.

The runtime complexity is as follows:

Operation Fibonacci-Heap
insert O(1)
getMin O(1)
extractMin O(log n) amortized
decreaseKey O(1) amortized
remove O(log n) amortized
merge O(1)

Since I wanted to implement routing algorithms (Dijkstra and A*) I have chosen Fibonacci Heaps because of the runtime behavior O(n * log(n) + m) instead of O( (n+m) * log(n)) when using Binomial Heaps.

Any recommendations / improvements are welcome. Feel free to contact me.