Skip to content
This is 3 implementations of shortest path algorithm in Python, Go and Nodejs
Go JavaScript Python
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
data
image
README.md
shortest.go
shortest.js
shortest.py

README.md

Shortest Path Algorithm

This repo contains 3 different implementation of shortest path algorithm in Python, Nodejs(JavaScript) and Golang(Go). The code included some test code for benchmark purpose, it also serves as an example on how to use the algorithm. For detail disussion on actual application of the algorithm, you could take a look at my blog post How to create an interactive transport system map with shortest path algorithm. The start and end nodes in the test code are two actual stations of Singapore Mass Rapid Transit (SMRT) system which can be visually seen here:

The shortest path between ns1/ew24 and ew2/dt32

To run the Golang test code:

go run shortest.go

To run the Nodejs test code:

node shortest.js

To run the Python test code:

python3 shortest.py

Performanace

The code was originally written in Python with the intention for running it on a Raspberry Pi 3B, the code was too slow to be used practically, and it was then ported to JavaScript and running on the client side with the assumption that any computer or even mobile phone nowadays is faster than a Raspberry Pi. I recently port it into Golang and run some benchmark on both Raspberry Pi and my MacBook Pro late 2011 model, here are the comparison of the test results.

Raspberry Pi 3 model B MacBook Pro
go1.12.6 node v8.11.1 python3.5.3 go1.12.1 node v10.13.0 python3.6.1
Time (sec) 1.968 6.568 16.653 0.382 1.209 2.314
2.072 6.624 16.711 0.392 1.210 2.159
1.969 6.576 16.619 0.394 1.189 2.363
2.021 6.582 16.650 0.383 1.164 2.255
1.965 6.602 16.751 0.388 1.188 2.262
1.990 6.614 16.656 0.380 1.217 2.285
2.031 6.592 16.573 0.407 1.186 2.235
1.964 6.562 16.854 0.401 1.195 2.221
1.957 6.645 16.889 0.408 1.187 2.205
1.962 6.562 16.624 0.397 1.161 2.201
Average (sec) 1.990 6.593 16.698 0.393 1.191 2.250
You can’t perform that action at this time.