-1

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

    openSet.add(current)
    openHeap.append((0,current))
    while openSet:
    print "come2"
        current = heapq.heappop(openHeap)[1]
        if current == end:
        print "come3"                   
        return retracePath(current)
        openSet.remove(current)
        closedSet.add(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:
                            openSet.add(tile)
                            heapq.heappush(openHeap, (tile.H,tile))
                    tile.parent = current
    return []
2
  • Please post your code again with correct indentation.
    – underdark
    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.
    – Alexandros
    Jun 7, 2014 at 20:05

1 Answer 1

2

You can use Networkx library.

http://networkx.github.io

It can read shapefiles. Ex:

import networkx

graph = networkx.read_shp("path/to/your/shapefile.shp")

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.