Zeta.Dijkstra.NET
1.2.1-pre
dotnet add package Zeta.Dijkstra.NET --version 1.2.1-pre
NuGet\Install-Package Zeta.Dijkstra.NET -Version 1.2.1-pre
<PackageReference Include="Zeta.Dijkstra.NET" Version="1.2.1-pre" />
paket add Zeta.Dijkstra.NET --version 1.2.1-pre
#r "nuget: Zeta.Dijkstra.NET, 1.2.1-pre"
// Install Zeta.Dijkstra.NET as a Cake Addin
#addin nuget:?package=Zeta.Dijkstra.NET&version=1.2.1-pre&prerelease
// Install Zeta.Dijkstra.NET as a Cake Tool
#tool nuget:?package=Zeta.Dijkstra.NET&version=1.2.1-pre&prerelease
Dijkstra.NET
Dijkstra algorithm which use priority queue thus complexity is equal O(ElogV) where E is number of edges and V is number of vertices. Used data structures are based on interfaces so you can implement your own or reused present. Simply example below. More information about algorithm you can find on Wikipedia.
Get Started
Install the latest version from NuGet
Install-Package Dijkstra.NET
Simple example
using Dijkstra.NET.Graph;
using Dijkstra.NET.ShortestPath;
var graph = new Graph<int, string>();
graph.AddNode(1);
graph.AddNode(2);
graph.Connect(1, 2, 5, "some custom information in edge"); //First node has key equal 1
ShortestPathResult result = graph.Dijkstra(1, 2); //result contains the shortest path
var path = result.GetPath();
or
using Dijkstra.NET.Graph;
using Dijkstra.NET.ShortestPath;
var graph = new Graph<int, string>() + 1 + 2;
bool connected = graph >> 1 >> 2 >> 5 ^ "custome edge information";
ShortestPathResult result = graph.Dijkstra(1, 2); //result contains the shortest path
var path = result.GetPath();
Benchmark
For Graph where number of nodes is 1 000 000 and connections between them 1 000 000. The length of path is minimum 10.
BenchmarkDotNet=v0.10.10, OS=Windows 10.0.17134
Processor=Intel Core i7-4700HQ CPU 2.40GHz (Haswell), ProcessorCount=8
Frequency=2338342 Hz, Resolution=427.6534 ns, Timer=TSC
[Host] : .NET Framework 4.6.1 (CLR 4.0.30319.42000), 32bit LegacyJIT-v4.7.3260.0
Job-XQYAYC : .NET Framework 4.6.1 (CLR 4.0.30319.42000), 32bit LegacyJIT-v4.7.3260.0
LaunchCount=1 RunStrategy=Monitoring TargetCount=3
WarmupCount=2
Method | Mean | Error | StdDev | Scaled | ScaledSD | Gen 0 | Gen 1 | Allocated |
---|---|---|---|---|---|---|---|---|
Dijkstra | 7.515 ms | 3.845 ms | 0.2173 ms | 1.00 | 0.00 | - | - | 48 KB |
PageRank | 1,139.983 ms | 762.417 ms | 43.0780 ms | 151.77 | 5.86 | 40000 | 40000 | 272365.8 KB |
License
Dijkstra.NET is licensed under the MIT license. See LICENSE file for full license information.
Product | Versions Compatible and additional computed target framework versions. |
---|---|
.NET | net5.0 was computed. net5.0-windows was computed. net6.0 was computed. net6.0-android was computed. net6.0-ios was computed. net6.0-maccatalyst was computed. net6.0-macos was computed. net6.0-tvos was computed. net6.0-windows was computed. net7.0 was computed. net7.0-android was computed. net7.0-ios was computed. net7.0-maccatalyst was computed. net7.0-macos was computed. net7.0-tvos was computed. net7.0-windows was computed. net8.0 was computed. net8.0-android was computed. net8.0-browser was computed. net8.0-ios was computed. net8.0-maccatalyst was computed. net8.0-macos was computed. net8.0-tvos was computed. net8.0-windows was computed. |
.NET Core | netcoreapp1.0 was computed. netcoreapp1.1 was computed. netcoreapp2.0 was computed. netcoreapp2.1 was computed. netcoreapp2.2 was computed. netcoreapp3.0 was computed. netcoreapp3.1 was computed. |
.NET Standard | netstandard1.3 is compatible. netstandard1.4 was computed. netstandard1.5 was computed. netstandard1.6 was computed. netstandard2.0 was computed. netstandard2.1 was computed. |
.NET Framework | net40 is compatible. net403 was computed. net45 was computed. net451 was computed. net452 was computed. net46 was computed. net461 was computed. net462 was computed. net463 was computed. net47 was computed. net471 was computed. net472 was computed. net48 was computed. net481 was computed. |
MonoAndroid | monoandroid was computed. |
MonoMac | monomac was computed. |
MonoTouch | monotouch was computed. |
Tizen | tizen30 was computed. tizen40 was computed. tizen60 was computed. |
Universal Windows Platform | uap was computed. uap10.0 was computed. |
Xamarin.iOS | xamarinios was computed. |
Xamarin.Mac | xamarinmac was computed. |
Xamarin.TVOS | xamarintvos was computed. |
Xamarin.WatchOS | xamarinwatchos was computed. |
-
.NETFramework 4.0
- No dependencies.
-
.NETStandard 1.3
- NETStandard.Library (>= 1.6.1)
NuGet packages
This package is not used by any NuGet packages.
GitHub repositories
This package is not used by any popular GitHub repositories.
Version | Downloads | Last updated |
---|