# Convert Road layer shapefile into a graph

I'm going to use Astar algorithm to find a path between two selected points.And I used the following code for that.Is there any way I could convert my Road Layer shapefile into a graph, which can be use in this function? I'm new to QGIS and please help me to find a solution to this problem.

``````def astarSearch(self, graphAstar, current, end):
openSet = set()
openHeap = []
closedSet = set()

def retracePath(c):
path = [c]
while c.parent is not None:
c = c.parent
path.append(c)
path.reverse()
return path

openHeap.append((0,current))
while openSet:
print "come2"
current = heapq.heappop(openHeap)
if current == end:
print "come3"
return retracePath(current)
openSet.remove(current)
for tile in graphAstar[current]:
print "come4"
if tile not in closedSet:
tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10
if tile not in openSet:
heapq.heappush(openHeap, (tile.H,tile))
tile.parent = current
return []
``````
• Please post your code again with correct indentation. Jun 7, 2014 at 12:43
• You are missing the basic for A*. There is a case that a node is on the OpenList already and later you find a shorter path for that node. In that case the position of the node in the priority queue should be improved. This operation is called DecreaseKey and your code does not take care of it. Jun 7, 2014 at 20:05

You can use Networkx library.

http://networkx.github.io

``````import networkx

``````

Now you can use your graph:

``````print graph.nodes()

[(X.X, Y.Y), (X.X, Y.Y)...]
``````

There are also few alghoritms implemented: Dijkstra, Bellman-Ford, A*

http://networkx.github.io/documentation/latest/reference/algorithms.shortest_paths.html

• I used networkx. But it always returned '[]' (according to my code) for me. why is that? Jun 7, 2014 at 17:42
• Please tell me a way except networkx, because it's not working for me.. Jun 8, 2014 at 12:13