Уведомления

Группа в Telegram: @pythonsu

#1 Ноя. 18, 2010 17:04:19

Vadim
От:
Зарегистрирован: 2010-11-18
Сообщения: 20
Репутация: +  0  -
Профиль   Отправить e-mail  

Поиск во взвешенном графе

Здравствуйте, мне требуется найти самый короткий путь в графе по весу ребер, вес может быть и отрицательный, подскажите пожалуйста, как реализовать алгоритм Флойда — Уоршелла ну или на крайняк алгоритм дейкстры, если граф определяется следующим классом

class evense():   #класс задающий ребро графа
def _init_(self, a=0, b=0):
self.cord = [a, b] # координаты ребра в графе
self.mass = 2 # вес ребра.
def isin(self, a): # проверка приндлежности вершины ребру
if self.cord[0] == a or self.cord[1] == a:
return 1
else:
return 0
class point(): # класс задающий вершину графа
def _init_(self, c = 0):
self.cord = c #координаты вершины
self.defect = 0 # булево значение, пройдена ли вершина 1-нет 0-да
def _getitem_(self):
return self.cord
class graph(): # класс задающий граф
def _init_(self):
self.points = [] # вершины графа
self.evenses = [] # ребра графа
def converttopoint(self, evense): #конвертация ребра графа в кортеж вершин
u = point()
v = point()
u._init_(evense.cord[0])
v._init_(evense.cord[1])
s = u, v
return s
def converttoevense(self, a, b): # конвертация 2ух вершин в ребро,
# нет проверки на возможность такого задания и не задается вес так как реализовать это вне функции менее накладно
evense = evense()
evense._init_(a.cord, b.cord)
return evense
def addevense(self, a=0, b=0): #Добавление ребра, и запись его вершин
# нет проверки на уникальность вершин так как она в самой функции добавления, стандартные значания defect = 1
newevense = evense()
newevense._init_(a, b)
c1 = point()
c2 = point()
c1._init_(newevense.cord[0])
c2._init_(newevense.cord[1])
c1.defect = 1
c2.defect = 1
self.addpoint(c1)
self.addpoint(c2)
if newevense not in self.evenses:
self.evenses.append(newevense)
def addpoint(self, c=0): # добавление вершины в граф
newpoint = point()
newpoint._init_(c)
if newpoint not in self.points:
self.points.append(newpoint)
def _get_(self): #преобразование списка вершин в список их номеров
s = []
for i in self.points:
s.append(str(i.cord))
return s
Питон начал изучать всего 3 дня назад, не судите строго, но основываясь на этих классах надо написать алгоритм



Отредактировано (Ноя. 18, 2010 17:05:33)

Офлайн

#2 Ноя. 19, 2010 19:31:25

Vadim
От:
Зарегистрирован: 2010-11-18
Сообщения: 20
Репутация: +  0  -
Профиль   Отправить e-mail  

Поиск во взвешенном графе

Вообщем написал алгоритм, если интересно код лежит в разделе > Python для новичков > Проекты на python + исходники для новичков



Отредактировано (Ноя. 19, 2010 19:44:51)

Офлайн

#3 Ноя. 19, 2010 23:51:20

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 9746
Репутация: +  843  -
Профиль   Отправить e-mail  

Поиск во взвешенном графе

if self.cord[0] == a or self.cord[1] == a:
if a in self.cord:
там вообще
def isin(self, a): # проверка приндлежности вершины ребру
return a in self.cord
    def _get_(self): #преобразование списка вершин в список их номеров
s = []
for i in self.points:
s.append(str(i.cord))
return s
    def _get_(self): #преобразование списка вершин в список их номеров
return [str(i.cord) for i in self.points]
class graph(): # класс задающий граф
class graph: # класс задающий граф
и его ещё желательно с большой буквы называть



Отредактировано (Ноя. 20, 2010 00:00:11)

Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version