Как правильно пропарсить лабиринт в граф?

У меня есть лабиринт в двумерном массиве. Как мне правильно его превратить в матрицу смежности, если вершины графа - каждый поворот? Вес ребра - расстояние между двумя вершинами. Его тоже надо получить. Это по сути игровая карта, дорожки из звездочек ограничены решетками - стенами. Мне надо преобразовать это все в граф для использования алгоритма Дейкстры. Отметить перекрестки и повороты отдельно я могу, но было бы лучше, чтобы и это происходило автоматически.