Hi, I'm Artur Olszak and this is my programming blog :-)
You can contact me here.
Some links: LinkedIn, GitHub, Stackoverflow, SoundCloud.

2014-08-26 12:39:22

Implementation of shortest path algorithm in Objective-C - based on Dijkstra's algorithm

"In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

This is analogous to the problem of finding the shortest path between two intersections on a road map: the graph's vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of its road segment." - Wikipedia

Last weekend I was looking for a simple implementation of shortest path algorithm on iOS. I was suprised that I was not able to find any working example with really clear and straightforward code. That was a really good opportunity to make my own.

The goal for me was to have simple, reusable class with object oriented API. I wanted to have also possibility to assign weight to connections between nodes in both directions - I didn't need that feature in the first place but still it was cool feature for me.

It was great to refresh my knowledge about Dynamic Programming and that kind of algorithms. I've looked at those methods for resolving shortest path problem:

After reading informations about those algorithms and finding some implementations in c++, it was clear for me that all I needed was provide code which will find all possible paths between two points and just choose the shortest one. I know that it sounds a bit like bruteforce method but that's how those methods mainly works. I wanted to implement algorithm closest to the Dijkstra's, because it was the most clear for me.

I've implemented three classes to accomplish my task:

  • AOShortestPath - class which holds logic for calculations and structure logic
  • AOPathPoint - representation of node
  • AOPathConnection - representation of connection between two nodes

During the process of creation I've made a sample code to debug and visualize the results of callculations. I've posted it on GitHub, code is here. Feel free to use it for yourself and add some new revisions the repository.


<-- back



Name
E-mail




2015-08-18 15:33:06

dupa



2015-08-18 15:32:50
dsfdsfsdfsd


Tom
2014-08-31 18:04:35
Thanks for sample code!


Since 2013