Convert Road layer shapefile into a graph

Question

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 []

Answer 1

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