Файл:DijkstraDemo.gif

''' Кратчайший путь покрытия Дейкстры (SVG) с использованием очереди приоритетов. Сначала используйте этот код для генерации кадров SVG. Затем преобразуйте в битовые изображения и конвертируйте в GIF. '''# размер диапазона N  =  500 поле  =  20def  norm ( px ,  py ):  return  (( px [ 0 ] - py [ 0 ]) ** 2 + ( px [ 1 ] - py [ 1 ]) ** 2 ) ** .5def  saveToSVG ( nFrames ,  points ,  edges ,  firmed ,  relax ):  f  =  open ( 'demo_' + '0' * ( 3 - len ( str ( nFrames ))) + str ( nFrames ) + '.svg' ,  'w' )  f.write ( "<svg xmlns= \" http : //www.w3.org/2000/svg \" version= \" 1.1 \" > \n " ) для p в точках : f . write ( "<circle cx= \" " + str ( p [ 0 ] + margin ) + " \" cy= \" " + str ( N - p [ 1 ] + margin ) + " \" r= \" 5 \" fill= \" white \" stroke= \" black \" /> \n " ) for i in range ( len ( edges )): for j in edge [ i ]: f .запись ( "<строка x1= \" " + str ( точки [ i ][ 0 ] + отступ ) + " \" y1= \" " + str ( N - точки [ i ][ 1 ] + отступ ) + " \" x2= \" " + str ( точки [ j ][ 0 ] + отступ ) + " \" y2= \"                          "  +  str ( N ​​- points [ j ][ 1 ] + margin )  +  " \" stroke= \" grey \" stroke-width= \" .5 \" /> \n " )  для  L  в  фиксированном состоянии :  f . write ( "<line x1= \" "  + str ( L [ 0 ][ 0 ] + margin ) +  " \" y1= \" " +  str ( N ​​- L [ 0 ][ 1 ] + margin )  + " \ " x2= \" "  +  str ( L [ 1 ][ 0 ] + margin )  +  " \" y2= \" " + str ( N ​​- L [ 1 ][ 1 ] + margin ) + " \" stroke= \" red \" stroke-width= \" 5 \" /> \n " ) для L в расслабленном состоянии : f .запись ( "<строка x1= \" " + str ( L [ 0 ][ 0 ] + margin ) + " \" y1= \" " + str ( N ​​- L [ 0 ][ 1 ] + margin ) + " \" x2= \" " + str ( L [ 1 ][ 0 ] + margin ) + " \" y2= \" " + str ( N                   - L [ 1 ][ 1 ] + margin )  +  " \" stroke= \" blue \" stroke-width= \" 5 \" /> \n " )  f . write ( "</svg> \n " )  f . close ()def  generatePoints ( n ):  импорт  случайных чисел  как  r  r . seed ( 10 )  res  =  []  для  i  в  диапазоне ( n ):  pt  =  [ r . randint ( 0 , N )  для  _  в  [ 0 ,  1 ]]  если  pt  не  в  res :  res  +=  [ pt ]  вернуть  res# эвристика: сосед с радиусом, например, N/3 def generateEdges (  n , points )  : импортировать  случайный  как  r  r.seed  ( 10 ) sides = [ ] for i in range ( n ): dst = [] for j in range ( n ) : if i != j and norm ( points [ i ] , points [ j ] ) < N / 3 : dst.append ( j ) ; sides.append ( dst ) return sides                         def  dijkstra ( n ,  points ,  sides ):  nframe  =  0  dist  =  [ float ( "inf" )  for  i  in  range ( n )]  prev  =  [ -1 for _ in range ( n )] cover = [] import heapq dist [ 0 ] = 0.0 heap = [[ dist [ i ]  , i ] for i in range ( n )] while len ( heap ) > 0 : u = heap [ 0 ] [ 1 ] if prev [ u ] !=- 1 : cover.append ([ points [ prev [ u ]], points [ u ]]) saveToSVG ( nframe , points , sides , cover , [ ]) nframe += 1 heapq . heappop ( куча ) для i в ребрах [ u ]: если i != u и dist [ i ] > dist [ u ] + norm ( points [ i ], points [ u ]): dist [ i ] = dist [ u ] + norm ( points [ i ], points [ u ]) prev [ i ] = u для j в диапазоне ( len ( куча )): if heap [ j ][                                                               1 ]  ==  i :  heap [ j ][ 0 ]  =  dist [ i ]  break  heapq . heapify ( heap )  saveToSVG ​​( nframe ,  points ,  sides ,  cover ,  [[ points [ u ],  points [ i ]]])  nframe += 1  возврат  расст. ,  пред.# тест 50 баллов временно n  =  50 баллов  =  generatePoints ( n ) es  =  generateEdges ( n ,  pts ) dijkstra ( n ,  pts ,  es )