Dijkstra's algorithm with Fibonacci heaps: an executable description in CHR

Jon Sneyers, Tom Schrijvers, Bart Demoen

Lirias (KU Leuven) · 2006 · 43 citations · 15 references

Full text

Open access

Concepts

Abstract

We construct a readable, compact and efficient implementation of Dijkstra's shortest path algorithm and Fibonacci heaps using Constraint Handling Rules (CHR), which is increasingly used as a high-level rule-based general-purpose programming language. We measure its performance in different CHR systems, investigating both the theoretical asymptotic complexity and the constant factors realized in practice.

References

15