Jennifer

Posted on

# Dijkstra's Algorithm + Web Assembly

Yea, I know what you are thinking ? why the heck am I so bent on shipping my C++ code to the web, well just for the fun of it 🙂

Alright Alright, let me start from the very beginning 😁. Sometime in mid 2020 at the heat of the pandemic, I was at home and bored, so I decided to implement data structures and algorithm in C++, started with Bellman-ford algorithm to sorting algorithms then Dijkstra, but I wasn't satisfied, I wanted real life applications so I decided to take the Dijkstra's algorithm to the web using data gotten from mileage charts.
the mileage chart data was a csv file that looks like this

I wrote the Dijkstra's algorithm in C++ using cmake, it worked quite well, takes two strings as input and displays the shortest distance with paths to follow, you can see code here
A brief summary of steps I took to achieve this:

• Read the csv file and convert it to a 2D table

• convert the table to adjacency list

• implement Dijkstra's algorithm on the adjacency list
The only problem I had was the fact that it was a command line application as shown

I wanted to ship it off to the web so bad, so I started researching for solutions
I came across restbed, but I wasn't satisfied with the results and restbed was soo confusing, I even tried converting it to a dll, and using the dll in the JavaScript frontend but that didn't work out either, because I obviously didn't know what I was doing 🤣

So fast forward to sometime in October 2021, I applied for Outreachy internship, during the contribution phase while trying to contribute to the Enarx project, I got introduced to web assembly, and I was like heck yea, this is what I need to complete my long lost Dijkstra's algorithm project !!

Okay... so how do we go about it ??, first was to setup my environment variable.

To compile C/C++ code to WebAssembly, I need a toolchain. This tool will be responsible for translating the code into WebAssembly format. To do that, I installed the Emscripten toolchain. It is an open-source project that can compile any portable C/C++ code into WebAssembly.

``````cd ~/
git clone https://github.com/emscripten-core/emsdk.git
cd emsdk
emsdk install latest
emsdk activate latest
``````

Add variables to PATH:

``````emsdk_env.bat             (windows)

source ./emsdk_env.sh      (unix)
``````

The updates that this makes to environment variables isn't persistent; it will need to be run again with the next reboot.

I created a build.sh file to make building easy for me

``````rm build/ -rf
mkdir build
cd build
em++ ../src/Dijkstra.cpp -g -std=c++1z -s WASM=1 -s
EXCEPTION_CATCHING_ALLOWED=[..] -o index.js || exit 1
``````

and serve.sh

``````emrun --port 8080 web/
``````

This will create three files: index.js, index.wasm and index.html.
index.wasm - the compiled version of your program

index.html - an HTML page for hosting your WebAssembly

index.js - JavaScript for loading your WebAssembly into the page

But note that index.html would not be recreated each time I rebuild.
Now, open the browser and access http://localhost:8080

The input will be gotten from the user from the front end (index.html) using Autocomplete function. see here
Embind was used to bind the C++ function to JavaScript and displayed for user as shown

And Yes 😄, I finally shipped my Dijkstra's algorithm to the web, you can see full code on github

## Latest comments (1)

Connor Hicks

This is so great! Thanks for sharing.