Shortest Path Algorithm Revisit with Golang

I wrote a shortest path algorithm about a year ago using Python and later on port it into JavaScript, I recently revisit the algorithm and port it into Golang and compare the performance of three versions on two different hardware platforms.

Shortest Path Algorithm with Python and Raspberry Pi

In my previous article that published almost a year ago, I wrote about How to create an interactive transport system map with shortest path algorithm. The algorithm was written in Python, and was fairly optimized based on Python code (or rather I don't know what I could do to further optimize it). It tooks any where from a few hundred milliseconds to roughly about 2 seconds to calculation the shortest path between two nodes (two subway stations) over about 100 nodes on my MacBook Pro which is a late 2011 model with a 2.4Hz Intel Core i5 CPU.

Python version


def shortest_path(graph, start, end, path=[]):
    if start not in graph.keys():
        return None
    path = path + [start]
    if start == end:
        return path
    shortest = None
    for node in graph[start]:
        if node not in path:
            new_path = shortest_path(graph, node, end, path)
            if new_path:
                if not shortest or len(new_path) < len(shortest):
                    shortest = new_path
    return shortest

As you probably awared that I run this blog on a Raspberry Pi 3 model B which has an ARMv7-based Brodcom BCM2837 SoC running at 1.2GHz. When I load the very same algorithm to the Raspberry Pi, the algorithm took 8 times longer to calculate the same shortest path than when running on my MacBook Pro. A 2 seconds calculation would became 16 seconds or longer to finish. This is obviously not practical and not a good user experience for a web application.

Porting Shortest Path Algorithm to JavaScript

So I port the algorithm to JavaScript with the assumption that any computer out there, desktop or notebook, or even a mobile phone nowsaday, would be more powerful and therefore faster than a Raspberry Pi.

JavaScript version


function calShortestPath(graph, start, end, path=[]) {
  if (!graph.hasOwnProperty(start)) {
    return [];
  }
  path = path.concat(start);
  if (start == end) {
    return path;
  }
  let shortest = [];
  for (let node of graph[start]) {
    if (path.indexOf(node) == -1) {
      let newPath = calShortestPath(graph, node, end, path);
      if (newPath.length > 0) {
        if ( shortest.length == 0 | (newPath.length < shortest.length) ) {
          shortest = newPath;
        }
      }
    }
  };
  return shortest;
}

Moving the algorithm from backend (running Python) to frontend (with JavaScript) sort of solved the performance problem, but I have to give up one of the features that was available in the Python web application (not directly related to the algorithm though). When I create the Interfactive map web application, I imagine that you could query the server through a GET request with an API through an endpoint like /api/v1/?start=ns1/ew24&end=ew2/dt2, and the server will return a shortest path JSON object that consists of a list of stations that formed the short test path between the two stations ns1/ew24 and ew2/dt2. The JavaScript solution works well for most of the cases, but the performance varies from user to user, depend on the machine/device he/she is using, for example, if you are using a relative old phone such as iPhone5, the performance is still a little bit too slow for what I consider a good user experience. So I always consider this as a short term solution and want to solve this problem, but I didn't do anything until recently.

Shortest Path Algorithm with Golang

Unlike Python and JavaScript, that are interpreted high-level programming languages, Golang or Go is a compiled programming language, designed with improving programming productivity (shorter build time) and runtime efficiency in mind. I recently start to tinkering with Golang and decided to revisit the shortest path algorithm with Golang.

Porting the algorithm from Python to Golang is kind of travia and the finished code looks still quite similar to the Python version, except that Golang does not have a build-in function for checking if a slice contains an element, such as Object.prototype.hasOwnProperty() in JavaScript, or accessing the view object of a Python Dictionary. For Golang, I have to create a custom type with a method to do that. The Golang code for the shortest algorithm with the helper method for the custom type is listed here:

Golang version


package main

import (
    "fmt"
)

type Array []string

func (arr Array) hasPropertyOf(str string) bool {
    for _, v := range arr {
        if str == v {
            return true
        }
    }
    return false
}

func ShortestPath(graph map[string][]string, start string, end string, path Array) []string {
    if _, exist := graph[start]; !exist {
        return path
    }
    path = append(path, start)
    if start == end {
        return path
    }
    shortest := make([]string, 0)
        for _, node := range graph[start] {
        if !path.hasPropertyOf(node) {
            newPath := ShortestPath(graph, node, end, path)
            if len(newPath) > 0 {
                if (len(shortest) == 0 || (len(newPath) < len(shortest))) {
                    shortest = newPath
                }
            }
        }
    }
    return shortest
}

Performance Comparison

I'm ready to do some performance comparison between Python, JavaScript and Golang. I wrote a simple program for each of the languages to test the time taken for calculating the shortest path. To not dupliate the code that already shown above, The following codes are ignore the function of each shortest path implementation, and only show the codes realted to load the graph data structure, and the code for testing in Python, Nodejs (for JavaScript) and Golang. The complete version of the codes are available at my github repo.

Python test


import json
import time


def load_graph(file_name):
    with open(file_name) as f:
        data = json.load(f)
        return data


stations = load_graph('./data/stations_sg.json')
s = time.time()
route = shortest_path(stations, "ns1/ew24", "ew2/dt32")
elapsed = time.time() - s
print(elapsed)
print(route)

Nodejs test


var fs = require('fs');

var s = "ns1/ew24";
var e = "ew2/dt32";
var p = [];
var graph = JSON.parse(fs.readFileSync('./data/stations_sg.json', 'utf8'));

const t = new Date();
var sp = calShortestPath(g, s, e, p);
const elapsed = new Date() - t;
console.log(elapsed);
console.log(sp);

Golang test


package main

import (
    "fmt"
    "time"
    "encoding/json"
    "io/ioutil"
    "os"
)

func ReadStationsData () map[string][]string {
    var stations map[string][]string

    jsonFile, err := os.Open("./data/stations_sg.json")
    defer jsonFile.Close()
    if err != nil {
        fmt.Println(err)
    }

    jsonBytes, _ := ioutil.ReadAll(jsonFile)
    json.Unmarshal([]byte(jsonBytes), &stations)
        return stations
}

func main() {

    graph := ReadStationsData()
    var s string = "ns1/ew24"
    var e string = "ew2/dt32"
    var path = make([]string, 0 , 50)

    startTime := time.Now()
    shortestPath := ShortestPath(graph, s, e, path)
    elapsed := time.Since(startTime)
    fmt.Println(shortestPath)
    fmt.Println(elapsed)

}

I picked two nodes (i.e. stations on the map) that are far apart and there are multiple paths available between the nodes, the starting node ns1/ew24 and the ending node ew2/dt32 and the shortest path can be visually seen on the following picture. I run each program 10 times and record the time taken for the algorithm to calculate the shortest path.

shortest path between two nodes visually

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
Raspberry Pi 3 model B MacBook Pro
go 1.12.6 node v8.11.1 python 3.5.3 go 1.12.1 node v10.13.0 python 3.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

The chart shows that when running on Macbook Pro, Golang algorithm on average took 393ms to calculate the shortest path, versus 1.191s for Nodejs and 2.25s for Python. In another word, Golang is about 3 times faster than Nodejs and about 5.7 times faster than Python.

The test on Raspberry Pi shown a similar result where Golang took 1.99s versus Nodejs' 6.953s, versus Python's 16.698s, it is 3.313 time faster than Nodejs, and 8.391 times faster than Python on Raspberry Pi.

On same programming language comparison on the two different platforms, Golang is roughly 5 times faster on MacBook Pro than Raspberry Pi, Nodejs is about 5.5 times faster on MacBook Pro than Raspberry Pi. For Python, MacBook Pro's result is 7.4 times faster than Raspberry Pi.

The tests give me a better understanding of Golang's performance on Raspberry Pi, and I will definitely consider to use Golang on Raspberry Pi for my future projects or even build a web service or web site using Golang in future.

Source codes

All source codes for the 3 implementations are available on my github Shortest Path Algorithm.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.