Персональные инструменты
 

Алгоритм Дейкстры — различия между версиями

Материал из CustisWiki

Перейти к: навигация, поиск
м (Трассировка алгоритма)
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
(не показаны 4 промежуточные версии 3 участников)
Строка 1: Строка 1:
Алгоритм Дейкстры (Dijkstra) предназначен для решения задачи [[Поиск кратчайших путей в графе]].
+
#REDIRECT [[discopal:{{PAGENAME}}]]
 
+
Важным фактом, позволяющим исключить перебор, является то, что если у нас есть кратчайший путь от ''v'' до ''w'', проходящий через вершину ''y'', назовем его <math>(v \rightarrow w)^*</math>, то его первая часть от ''v'' до ''y'', <math>(v \rightarrow y)^*</math>, тоже будет кратчайшим путем. Действительно, если бы это было не так, т.е. существовал бы путь <math>(v \rightarrow y)^!</math> длины меньшей, чем <math>(v \rightarrow y)^*</math>, то можно было бы улучшить оптимальный путь <math>(v \rightarrow w)^*</math>, заменив в нем <math>(v \rightarrow y)^*</math> на <math>(v \rightarrow y)^!</math>
+
(См. [[#Рисунок 1]]).
+
 
+
В алгоритме Дейкстры, мы, итерационно поддерживаем два множества вершин:
+
 
+
;Visited: множество вершин, до которых мы уже нашли кратчайший путь, ассоциированных со стоимостями кратчайших путей от стартовой вершины до них.
+
;ToVisit: множество вершин, которые достижимы одним ребром из множества вершин ''Visited'', ассоциированных с верхними оценками стоимости пути до них.
+
 
+
На каждой итерации, мы выбираем из достижимых вершин вершину ''v'', самую ближайшую к стартовой вершине ''s'', и переносим ее из множества ''ToVisit'' в множество ''Visited'', увеличиваем множество «кандидатов» ''ToVisit'' ее соседями, и пересчитываем верхнюю оценку удаленности вершин из ''ToVisit'' до вершины ''s''.
+
 
+
В иллюстрации выполнения алгоритма, мы показываем изменение на каждой итерации хэш-таблиц ''Visited'' и ''ToVisit'', а в конце изображен входной граф, где сплошными линиями нарисованы имеющиеся ребра с ассоциированными длинами, а пунктиром — найденные кратчайшие пути.
+
 
+
Важно, что алгоритм работоспособен только в случае положительных расстояний, в противном случае, можно попробовать использовать [[алгоритм Флойда-Уоршолла]].
+
 
+
Код алгоритма, представлен в виде функции на языке [[Python]].
+
 
+
<code-python>
+
def dijkstra(G,start_node):
+
    # хэш (узел -> стоимость) посещенных вершин
+
    Visited={}             
+
    # хэш (узел -> стоимость) ближайших к посещенным
+
    ToVisit={start_node:0}        
+
    # хэш (узел -> кратчайший путь)
+
    Paths = {start_node:[start_node]}  
+
    # пока есть вершины, до которых не построен кратчайший путь
+
    while ToVisit: 
+
        # выбираем ближайшую
+
        v=argmin(ToVisit)     
+
        # до $v$ кратчайший путь найден
+
        Visited[v]=ToVisit[v]; del ToVisit[v]; 
+
        # для всех соседей вершины $v$
+
        for w in G.neighbors(v):
+
            # к которым еще не нашли кратчайший путь   
+
            if (w not in Visited): 
+
                # обновляем кратчайшие пути
+
                vwLength = Visited[v] + G.get_edge(v,w)
+
                if (w not in ToVisit) or (vwLength < ToVisit[w]):
+
                    ToVisit[w] = vwLength
+
                    Paths[w] = Paths[v]+[w]
+
        print_frame(G, start_node, Visited, ToVisit, Paths)
+
    return (Visited,Paths)
+
</code-python>
+
 
+
==Трассировка алгоритма==
+
Последовательность итераций алгоритма показана ниже. В голубой цвет выкрашены вершины из «Visited» (причем указана стоимость их достижения), в желтый — из «ToVisit» (указана минимально известная стоимость их достижения для данной итерации). Также выделены ребра, принадлежащие кратчайшим путям.
+
 
+
===Итерация 1===
+
 
+
<neato>
+
graph G{ rankdir=TB; overlap=scale; rankdir=TB; splines=true;
+
        edge[len=3,fontcolor="blue",style="dashed"];
+
        node[fontcolor="red"];
+
 
+
   
+
            0 [label="NY", ];
+
       
+
            1 [label="Moscow\n $15",  style=filled, fillcolor="yellow" ];
+
       
+
            2 [label="Minsk\n Start\n $0",  shape=box, periferies=2  style=filled, fillcolor="lightblue" ];
+
       
+
            3 [label="Berlin\n $20",  style=filled, fillcolor="yellow" ];
+
       
+
            4 [label="Kiev\n $15",  style=filled, fillcolor="yellow" ];
+
       
+
            5 [label="Munich", ];
+
       
+
            6 [label="Vladivostok", ];
+
       
+
   
+
            0 -- 1 [label="$60", ];
+
       
+
            0 -- 3 [label="$50", ];
+
       
+
            0 -- 6 [label="$30", ];
+
       
+
            1 -- 2 [label="$15", ];
+
       
+
            1 -- 3 [label="$50", ];
+
       
+
            1 -- 4 [label="$10", ];
+
       
+
            1 -- 6 [label="$105", ];
+
       
+
            2 -- 3 [label="$20", ];
+
       
+
            2 -- 4 [label="$15", ];
+
       
+
            3 -- 4 [label="$30", ];
+
       
+
            3 -- 5 [label="$10", ];
+
       
+
    }
+
</neato>
+
 
+
===Итерация 2===
+
<neato>
+
graph G{ rankdir=TB; overlap=scale; rankdir=TB; splines=true;
+
        edge[len=3,fontcolor="blue",style="dashed"];
+
        node[fontcolor="red"];
+
 
+
   
+
            0 [label="NY\n $75",  style=filled, fillcolor="yellow" ];
+
       
+
            1 [label="Moscow\n $15",  style=filled, fillcolor="lightblue" ];
+
       
+
            2 [label="Minsk\n Start\n $0",  shape=box, periferies=2  style=filled, fillcolor="lightblue" ];
+
       
+
            3 [label="Berlin\n $20",  style=filled, fillcolor="yellow" ];
+
       
+
            4 [label="Kiev\n $15",  style=filled, fillcolor="yellow" ];
+
       
+
            5 [label="Munich", ];
+
       
+
            6 [label="Vladivostok\n $120",  style=filled, fillcolor="yellow" ];
+
       
+
   
+
            0 -- 1 [label="$60", ];
+
       
+
            0 -- 3 [label="$50", ];
+
       
+
            0 -- 6 [label="$30", ];
+
       
+
            1 -- 2 [label="$15", style="bold"];
+
       
+
            1 -- 3 [label="$50", ];
+
       
+
            1 -- 4 [label="$10", ];
+
       
+
            1 -- 6 [label="$105", ];
+
       
+
            2 -- 3 [label="$20", ];
+
       
+
            2 -- 4 [label="$15", ];
+
       
+
            3 -- 4 [label="$30", ];
+
       
+
            3 -- 5 [label="$10", ];
+
       
+
    }
+
</neato>
+
 
+
===Итерация 3===
+
<neato>
+
graph G{ rankdir=TB; overlap=scale; rankdir=TB; splines=true;
+
        edge[len=3,fontcolor="blue",style="dashed"];
+
        node[fontcolor="red"];
+
 
+
   
+
            0 [label="NY\n $75",  style=filled, fillcolor="yellow" ];
+
       
+
            1 [label="Moscow\n $15",  style=filled, fillcolor="lightblue" ];
+
       
+
            2 [label="Minsk\n Start\n $0",  shape=box, periferies=2  style=filled, fillcolor="lightblue" ];
+
       
+
            3 [label="Berlin\n $20",  style=filled, fillcolor="yellow" ];
+
       
+
            4 [label="Kiev\n $15",  style=filled, fillcolor="lightblue" ];
+
       
+
            5 [label="Munich", ];
+
       
+
            6 [label="Vladivostok\n $120",  style=filled, fillcolor="yellow" ];
+
       
+
   
+
            0 -- 1 [label="$60", ];
+
       
+
            0 -- 3 [label="$50", ];
+
       
+
            0 -- 6 [label="$30", ];
+
       
+
            1 -- 2 [label="$15", style="bold"];
+
       
+
            1 -- 3 [label="$50", ];
+
       
+
            1 -- 4 [label="$10", ];
+
       
+
            1 -- 6 [label="$105", ];
+
       
+
            2 -- 3 [label="$20", ];
+
       
+
            2 -- 4 [label="$15", style="bold"];
+
       
+
            3 -- 4 [label="$30", ];
+
       
+
            3 -- 5 [label="$10", ];
+
       
+
    }
+
</neato>
+
 
+
===Итерация 4===
+
<neato>
+
graph G{ rankdir=TB; overlap=scale; rankdir=TB; splines=true;
+
        edge[len=3,fontcolor="blue",style="dashed"];
+
        node[fontcolor="red"];
+
 
+
   
+
            0 [label="NY\n $70",  style=filled, fillcolor="yellow" ];
+
       
+
            1 [label="Moscow\n $15",  style=filled, fillcolor="lightblue" ];
+
       
+
            2 [label="Minsk\n Start\n $0",  shape=box, periferies=2  style=filled, fillcolor="lightblue" ];
+
       
+
            3 [label="Berlin\n $20",  style=filled, fillcolor="lightblue" ];
+
       
+
            4 [label="Kiev\n $15",  style=filled, fillcolor="lightblue" ];
+
       
+
            5 [label="Munich\n $30",  style=filled, fillcolor="yellow" ];
+
       
+
            6 [label="Vladivostok\n $120",  style=filled, fillcolor="yellow" ];
+
       
+
   
+
            0 -- 1 [label="$60", ];
+
       
+
            0 -- 3 [label="$50", ];
+
       
+
            0 -- 6 [label="$30", ];
+
       
+
            1 -- 2 [label="$15", style="bold"];
+
       
+
            1 -- 3 [label="$50", ];
+
       
+
            1 -- 4 [label="$10", ];
+
       
+
            1 -- 6 [label="$105", ];
+
       
+
            2 -- 3 [label="$20", style="bold"];
+
       
+
            2 -- 4 [label="$15", style="bold"];
+
       
+
            3 -- 4 [label="$30", ];
+
       
+
            3 -- 5 [label="$10", ];
+
       
+
    }
+
</neato>
+
 
+
===Итерация 5===
+
<neato>
+
graph G{ rankdir=TB; overlap=scale; rankdir=TB; splines=true;
+
        edge[len=3,fontcolor="blue",style="dashed"];
+
        node[fontcolor="red"];
+
 
+
   
+
            0 [label="NY\n $70",  style=filled, fillcolor="yellow" ];
+
       
+
            1 [label="Moscow\n $15",  style=filled, fillcolor="lightblue" ];
+
       
+
            2 [label="Minsk\n Start\n $0",  shape=box, periferies=2  style=filled, fillcolor="lightblue" ];
+
       
+
            3 [label="Berlin\n $20",  style=filled, fillcolor="lightblue" ];
+
       
+
            4 [label="Kiev\n $15",  style=filled, fillcolor="lightblue" ];
+
       
+
            5 [label="Munich\n $30",  style=filled, fillcolor="lightblue" ];
+
       
+
            6 [label="Vladivostok\n $120",  style=filled, fillcolor="yellow" ];
+
       
+
   
+
            0 -- 1 [label="$60", ];
+
       
+
            0 -- 3 [label="$50", ];
+
       
+
            0 -- 6 [label="$30", ];
+
       
+
            1 -- 2 [label="$15", style="bold"];
+
       
+
            1 -- 3 [label="$50", ];
+
       
+
            1 -- 4 [label="$10", ];
+
       
+
            1 -- 6 [label="$105", ];
+
       
+
            2 -- 3 [label="$20", style="bold"];
+
       
+
            2 -- 4 [label="$15", style="bold"];
+
       
+
            3 -- 4 [label="$30", ];
+
       
+
            3 -- 5 [label="$10", style="bold"];
+
       
+
    }
+
</neato>
+
 
+
===Итерация 6===
+
<neato>
+
graph G{ rankdir=TB; overlap=scale; rankdir=TB; splines=true;
+
        edge[len=3,fontcolor="blue",style="dashed"];
+
        node[fontcolor="red"];
+
 
+
   
+
            0 [label="NY\n $70",  style=filled, fillcolor="lightblue" ];
+
       
+
            1 [label="Moscow\n $15",  style=filled, fillcolor="lightblue" ];
+
       
+
            2 [label="Minsk\n Start\n $0",  shape=box, periferies=2  style=filled, fillcolor="lightblue" ];
+
       
+
            3 [label="Berlin\n $20",  style=filled, fillcolor="lightblue" ];
+
       
+
            4 [label="Kiev\n $15",  style=filled, fillcolor="lightblue" ];
+
       
+
            5 [label="Munich\n $30",  style=filled, fillcolor="lightblue" ];
+
       
+
            6 [label="Vladivostok\n $100",  style=filled, fillcolor="yellow" ];
+
       
+
   
+
            0 -- 1 [label="$60", ];
+
       
+
            0 -- 3 [label="$50", style="bold"];
+
       
+
            0 -- 6 [label="$30", ];
+
       
+
            1 -- 2 [label="$15", style="bold"];
+
       
+
            1 -- 3 [label="$50", ];
+
       
+
            1 -- 4 [label="$10", ];
+
       
+
            1 -- 6 [label="$105", ];
+
       
+
            2 -- 3 [label="$20", style="bold"];
+
       
+
            2 -- 4 [label="$15", style="bold"];
+
       
+
            3 -- 4 [label="$30", ];
+
       
+
            3 -- 5 [label="$10", style="bold"];
+
       
+
    }
+
</neato>
+
 
+
 
+
===Итерация 7===
+
<neato>
+
graph G{ rankdir=TB; overlap=scale; rankdir=TB; splines=true;
+
        edge[len=3,fontcolor="blue",style="dashed"];
+
        node[fontcolor="red"];
+
 
+
   
+
            0 [label="NY\n $70",  style=filled, fillcolor="lightblue" ];
+
       
+
            1 [label="Moscow\n $15",  style=filled, fillcolor="lightblue" ];
+
       
+
            2 [label="Minsk\n Start\n $0",  shape=box, periferies=2  style=filled, fillcolor="lightblue" ];
+
       
+
            3 [label="Berlin\n $20",  style=filled, fillcolor="lightblue" ];
+
       
+
            4 [label="Kiev\n $15",  style=filled, fillcolor="lightblue" ];
+
       
+
            5 [label="Munich\n $30",  style=filled, fillcolor="lightblue" ];
+
       
+
            6 [label="Vladivostok\n $100",  style=filled, fillcolor="lightblue" ];
+
       
+
   
+
            0 -- 1 [label="$60", ];
+
       
+
            0 -- 3 [label="$50", style="bold"];
+
       
+
            0 -- 6 [label="$30", style="bold"];
+
       
+
            1 -- 2 [label="$15", style="bold"];
+
       
+
            1 -- 3 [label="$50", ];
+
       
+
            1 -- 4 [label="$10", ];
+
       
+
            1 -- 6 [label="$105", ];
+
       
+
            2 -- 3 [label="$20", style="bold"];
+
       
+
            2 -- 4 [label="$15", style="bold"];
+
       
+
            3 -- 4 [label="$30", ];
+
       
+
            3 -- 5 [label="$10", style="bold"];
+
       
+
    }
+
</neato>
+
 
+
==Рисунок 1==
+
 
+
<pic-svg>
+
<svg
+
  xmlns:dc="http://purl.org/dc/elements/1.1/"
+
  xmlns:cc="http://web.resource.org/cc/"
+
  xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
+
  xmlns:svg="http://www.w3.org/2000/svg"
+
  xmlns="http://www.w3.org/2000/svg"
+
  xmlns:sodipodi="http://inkscape.sourceforge.net/DTD/sodipodi-0.dtd"
+
  xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
+
  width="744.09448819"
+
  height="1052.3622047"
+
  id="svg2"
+
  sodipodi:version="0.32"
+
  inkscape:version="0.42.2"
+
  sodipodi:docbase="D:\myprojects\discopal\tex\lectures-cs\pic-svg"
+
  sodipodi:docname="dijkstra-pic-1.svg"
+
  inkscape:export-filename="D:\myprojects\discopal\tex\lectures-cs\pic-svg\test.png"
+
  inkscape:export-xdpi="90.000000"
+
  inkscape:export-ydpi="90.000000">
+
  <defs
+
    id="defs4">
+
    <marker
+
      inkscape:stockid="Arrow2Mend"
+
      orient="auto"
+
      refY="0.0"
+
      refX="0.0"
+
      id="Arrow2Mend"
+
      style="overflow:visible;">
+
      <path
+
        sodipodi:nodetypes="cccc"
+
        id="path14660"
+
        style="font-size:12.0;fill-rule:evenodd;stroke-width:0.62500000;stroke-linejoin:round;"
+
        d="M 8.7185878,4.0337352 L -2.2072895,0.016013256 L 8.7185884,-4.0017078 C 6.9730900,-1.6296469 6.9831476,1.6157441 8.7185878,4.0337352 z "
+
        transform="scale(0.6) rotate(180) translate(-5,0)" />
+
    </marker>
+
    <marker
+
      inkscape:stockid="Arrow1Lstart"
+
      orient="auto"
+
      refY="0.0"
+
      refX="0.0"
+
      id="Arrow1Lstart"
+
      style="overflow:visible">
+
      <path
+
        sodipodi:nodetypes="ccccc"
+
        id="path14671"
+
        d="M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z "
+
        style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;marker-start:none"
+
        transform="scale(0.8)" />
+
    </marker>
+
    <linearGradient
+
      id="linearGradient2108">
+
      <stop
+
        id="stop2110"
+
        offset="0"
+
        style="stop-color:#000000;stop-opacity:1;" />
+
      <stop
+
        id="stop2112"
+
        offset="1"
+
        style="stop-color:#000000;stop-opacity:0;" />
+
    </linearGradient>
+
    <linearGradient
+
      id="linearGradient2100">
+
      <stop
+
        style="stop-color:#000000;stop-opacity:1;"
+
        offset="0"
+
        id="stop2102" />
+
      <stop
+
        style="stop-color:#000000;stop-opacity:0;"
+
        offset="1"
+
        id="stop2104" />
+
    </linearGradient>
+
    <marker
+
      id="Triangle"
+
      viewBox="0 0 10 10"
+
      refX="0"
+
      refY="5"
+
      markerUnits="strokeWidth"
+
      markerWidth="4"
+
      markerHeight="3"
+
      orient="auto">
+
      <path
+
        d="M 0 0 L 10 5 L 0 10 z"
+
        id="path13771" />
+
    </marker>
+
  </defs>
+
  <sodipodi:namedview
+
    id="base"
+
    pagecolor="#ffffff"
+
    bordercolor="#666666"
+
    borderopacity="1.0"
+
    inkscape:pageopacity="0.0"
+
    inkscape:pageshadow="2"
+
    inkscape:zoom="2.5046296"
+
    inkscape:cx="278.00000"
+
    inkscape:cy="996.86691"
+
    inkscape:document-units="px"
+
    inkscape:current-layer="layer1"
+
    inkscape:window-width="1024"
+
    inkscape:window-height="708"
+
    inkscape:window-x="-4"
+
    inkscape:window-y="-4"
+
    inkscape:grid-points="true"
+
    inkscape:grid-bbox="true"
+
    showgrid="true"
+
    gridspacingx="3.0000000px"
+
    gridspacingy="3.0000000px" />
+
  <metadata
+
    id="metadata7">
+
    <rdf:RDF>
+
      <cc:Work
+
        rdf:about="">
+
        <dc:format>image/svg+xml</dc:format>
+
        <dc:type
+
          rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
+
      </cc:Work>
+
    </rdf:RDF>
+
  </metadata>
+
  <g
+
    inkscape:label="Layer 1"
+
    inkscape:groupmode="layer"
+
    id="layer1">
+
    <path
+
      style="fill:none;fill-opacity:0.75000000;fill-rule:evenodd;stroke:#000000;stroke-width:1.0000000;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4.0000000;stroke-dasharray:none;stroke-opacity:1.0000000"
+
      d="M 119.44880,88.862183 C 145.87403,62.957393 137.92053,69.405573 144.50857,64.238483"
+
      id="path4370"
+
      sodipodi:nodetypes="cs" />
+
    <path
+
      style="fill:#8093e2;fill-opacity:1.0000000;stroke:#0a0a0a;stroke-opacity:1.0000000"
+
      transform="translate(55.45548,-106.5736)"
+
      d="M 110.00000 165.08202 A 10.000000 8.2801600 0 1 1  90.000000,165.08202 A 10.000000 8.2801600 0 1 1  110.00000 165.08202 z"
+
      sodipodi:ry="8.2801600"
+
      sodipodi:rx="10.000000"
+
      sodipodi:cy="165.08202"
+
      sodipodi:cx="100.00000"
+
      id="path1738"
+
      sodipodi:type="arc" />
+
    <path
+
      style="fill:#8093e2;fill-opacity:1.0000000;stroke:#0a0a0a;stroke-opacity:1.0000000"
+
      transform="translate(186.8410,-48.65182)"
+
      d="M 110.00000 165.08202 A 10.000000 8.2801600 0 1 1  90.000000,165.08202 A 10.000000 8.2801600 0 1 1  110.00000 165.08202 z"
+
      sodipodi:ry="8.2801600"
+
      sodipodi:rx="10.000000"
+
      sodipodi:cy="165.08202"
+
      sodipodi:cx="100.00000"
+
      id="path1742"
+
      sodipodi:type="arc" />
+
    <g
+
      id="g1752"
+
      transform="translate(-112.1240,-64.52081)">
+
      <path
+
        style="fill:#8093e2;fill-opacity:1.0000000;stroke:#0a0a0a;stroke-opacity:1.0000000"
+
        transform="translate(122.7172,-6.719833)"
+
        d="M 110.00000 165.08202 A 10.000000 8.2801600 0 1 1  90.000000,165.08202 A 10.000000 8.2801600 0 1 1  110.00000 165.08202 z"
+
        sodipodi:ry="8.2801600"
+
        sodipodi:rx="10.000000"
+
        sodipodi:cy="165.08202"
+
        sodipodi:cx="100.00000"
+
        id="path4310"
+
        sodipodi:type="arc" />
+
      <text
+
        id="text1744"
+
        y="161.92468"
+
        x="219"
+
        style="font-size:12.000000px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1.0000000;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000;font-family:Bitstream Vera Sans"
+
        xml:space="preserve"><tspan
+
          y="161.92468"
+
          x="219.00000"
+
          id="tspan1746"
+
          sodipodi:role="line">v</tspan></text>
+
    </g>
+
    <g
+
      id="g1757"
+
      transform="translate(35.62708,-44.21805)">
+
      <path
+
        style="fill:#8093e2;fill-opacity:1.0000000;stroke:#0a0a0a;stroke-opacity:1.0000000"
+
        transform="translate(197.7139,-36.93967)"
+
        d="M 110.00000 165.08202 A 10.000000 8.2801600 0 1 1  90.000000,165.08202 A 10.000000 8.2801600 0 1 1  110.00000 165.08202 z"
+
        sodipodi:ry="8.2801600"
+
        sodipodi:rx="10.000000"
+
        sodipodi:cy="165.08202"
+
        sodipodi:cx="100.00000"
+
        id="path1736"
+
        sodipodi:type="arc" />
+
      <text
+
        id="text1748"
+
        y="130.94392"
+
        x="294"
+
        style="font-size:12.000000px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1.0000000;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000;font-family:Bitstream Vera Sans"
+
        xml:space="preserve"><tspan
+
          y="130.94392"
+
          x="294.00000"
+
          id="tspan1750"
+
          sodipodi:role="line">y</tspan></text>
+
    </g>
+
    <g
+
      id="g1768"
+
      transform="translate(-0.409840,-68.64281)">
+
      <path
+
        sodipodi:type="arc"
+
        id="path1734"
+
        sodipodi:cx="100.00000"
+
        sodipodi:cy="165.08202"
+
        sodipodi:rx="10.000000"
+
        sodipodi:ry="8.2801600"
+
        d="M 110.00000 165.08202 A 10.000000 8.2801600 0 1 1  90.000000,165.08202 A 10.000000 8.2801600 0 1 1  110.00000 165.08202 z"
+
        transform="translate(299.0000,-7.998361)"
+
        style="fill:#8093e2;fill-opacity:1.0000000;stroke:#0a0a0a;stroke-opacity:1.0000000" />
+
      <text
+
        id="text1762"
+
        y="160.49886"
+
        x="394.64517"
+
        style="font-size:12.000000px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1.0000000;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000;font-family:Bitstream Vera Sans"
+
        xml:space="preserve"><tspan
+
          y="160.49886"
+
          x="394.64517"
+
          id="tspan1764"
+
          sodipodi:role="line">w</tspan><tspan
+
          id="tspan1766"
+
          y="175.49886"
+
          x="394.64517"
+
          sodipodi:role="line" /></text>
+
    </g>
+
    <path
+
      sodipodi:nodetypes="cs"
+
      id="path1774"
+
      d="M 165.15398,61.741913 C 194.22703,68.946503 185.47658,67.153163 192.72475,68.590213"
+
      style="fill:none;fill-opacity:0.75000000;fill-rule:evenodd;stroke:#000000;stroke-width:1.0000000;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4.0000000;stroke-dasharray:none;stroke-opacity:1.0000000" />
+
    <path
+
      style="fill:none;fill-opacity:0.75000000;fill-rule:evenodd;stroke:#db1434;stroke-width:1.3224938;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4.0000000;stroke-dasharray:2.6449876 1.3224938 ;stroke-dashoffset:0.00000000;stroke-opacity:1.0000000"
+
      d="M 204.15661,39.523243 C 201.68696,39.230203 195.56210,40.038793 191.98693,41.325113 C 188.21875,42.680883 186.83566,44.174643 185.49097,47.631683 C 184.46549,50.268063 188.45432,54.807533 190.24841,56.356413 C 192.25082,58.085163 194.36311,60.458483 195.46398,62.497133 C 197.02765,65.392823 198.44460,68.161063 199.52054,71.506513 C 200.03591,73.108953 194.58168,76.397963 192.56644,77.813073 C 188.88364,80.399133 186.79304,83.130633 185.03283,86.672243 C 183.43107,89.895043 183.58009,94.818213 184.45332,98.332173 C 185.21315,101.38976 185.51736,102.92815 188.49097,105.32813 C 191.47339,107.73523 193.92673,109.68627 196.62300,111.14773 C 199.66985,112.79924 200.49097,116.16109 200.49097,119.32005 C 200.49097,122.80859 198.64876,124.81456 196.62300,126.91414 C 193.88871,129.74806 190.92468,133.02202 187.93037,135.64395 C 185.72772,137.57268 184.26794,140.26593 183.29431,141.77960"
+
      id="path1788" />
+
    <path
+
      style="fill:none;fill-opacity:0.75000000;fill-rule:evenodd;stroke:#000000;stroke-width:1.0000000;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4.0000000;stroke-dasharray:none;stroke-opacity:1.0000000"
+
      d="M 254.68568,74.526763 C 324.50363,83.655223 303.48975,81.382983 320.89595,83.203793"
+
      id="path1792"
+
      sodipodi:nodetypes="cs" />
+
    <path
+
      sodipodi:nodetypes="cs"
+
      id="path1794"
+
      d="M 120.07604,96.346043 C 190.79839,110.12213 169.51228,106.69299 187.14397,109.44084"
+
      style="opacity:1.0000000;fill:none;fill-opacity:0.75000000;fill-rule:evenodd;stroke:#5121ef;stroke-width:1.3940229;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4.0000000;stroke-dasharray:1.3940229 1.3940229 ;stroke-dashoffset:2.2304368;stroke-opacity:1.0000000" />
+
    <path
+
      style="opacity:1.0000000;fill:none;fill-opacity:0.75000000;fill-rule:evenodd;stroke:#5121ef;stroke-width:0.90512192;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4.0000000;stroke-dasharray:0.90512190 0.90512190 ;stroke-dashoffset:1.4481950;stroke-opacity:1.0000000"
+
      d="M 249.53908,111.91835 C 276.88604,114.62350 268.65512,113.95014 275.47295,114.48972"
+
      id="path3332"
+
      sodipodi:nodetypes="cs" />
+
    <path
+
      sodipodi:nodetypes="cs"
+
      id="path3334"
+
      d="M 296.95279,116.17504 C 327.02810,91.881893 317.97600,97.928903 325.47403,93.083293"
+
      style="opacity:1.0000000;fill:none;fill-opacity:0.75000000;fill-rule:evenodd;stroke:#5121ef;stroke-width:1.2071885;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4.0000000;stroke-dasharray:1.2071885 1.2071885 ;stroke-dashoffset:1.9315017;stroke-opacity:1.0000000" />
+
    <path
+
      id="path4080"
+
      d="M 262.17973,50.117753 C 259.71008,49.842733 253.58522,50.601593 250.01005,51.808793 C 246.24187,53.081173 244.85878,54.483053 243.51409,57.727453 C 242.48861,60.201683 246.47744,64.461933 248.27153,65.915553 C 250.27394,67.537963 252.38623,69.765313 253.48710,71.678563 C 255.05077,74.396153 256.46772,76.994123 257.54366,80.133803 C 258.05903,81.637683 252.60480,84.724393 250.58956,86.052463 C 246.90676,88.479453 244.81616,91.042943 243.05595,94.366723 C 241.45419,97.391293 241.60321,102.01165 242.47644,105.30947 C 243.23627,108.17900 243.54048,109.62276 246.51409,111.87513 C 249.49651,114.13417 251.94985,115.96521 254.64612,117.33678 C 257.69297,118.88671 258.51409,122.04178 258.51409,125.00644 C 258.51409,128.28040 256.67188,130.16299 254.64612,132.13343 C 251.91183,134.79304 248.94780,137.86563 245.95349,140.32629 C 243.75084,142.13639 242.29106,144.66398 241.31743,146.08455"
+
      style="fill:none;fill-opacity:0.75000000;fill-rule:evenodd;stroke:#db1434;stroke-width:1.2811766;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4.0000000;stroke-dasharray:2.5623532 1.2811766 ;stroke-dashoffset:0.00000000;stroke-opacity:1.0000000" />
+
    <path
+
      sodipodi:nodetypes="cs"
+
      id="path4082"
+
      d="M 342.11839,85.659933 C 388.71033,89.520033 374.68704,88.559183 386.30280,89.329143"
+
      style="fill:none;fill-opacity:0.75000000;fill-rule:evenodd;stroke:#000000;stroke-width:1.0000000;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4.0000000;stroke-dasharray:none;stroke-opacity:1.0000000" />
+
    <path
+
      sodipodi:type="arc"
+
      id="path6316"
+
      sodipodi:cx="100.00000"
+
      sodipodi:cy="165.08202"
+
      sodipodi:rx="10.000000"
+
      sodipodi:ry="8.2801600"
+
      d="M 110.00000 165.08202 A 10.000000 8.2801600 0 1 1  90.000000,165.08202 A 10.000000 8.2801600 0 1 1  110.00000 165.08202 z"
+
      transform="matrix(0.285714,0.000000,0.000000,0.316641,171.2696,30.38896)"
+
      style="fill:#8093e2;fill-opacity:1.0000000;stroke:#0a0a0a;stroke-opacity:1.0000000" />
+
    <path
+
      style="fill:#8093e2;fill-opacity:1.0000000;stroke:#0a0a0a;stroke-opacity:1.0000000"
+
      transform="matrix(0.285714,0.000000,0.000000,0.316641,184.5983,25.75289)"
+
      d="M 110.00000 165.08202 A 10.000000 8.2801600 0 1 1  90.000000,165.08202 A 10.000000 8.2801600 0 1 1  110.00000 165.08202 z"
+
      sodipodi:ry="8.2801600"
+
      sodipodi:rx="10.000000"
+
      sodipodi:cy="165.08202"
+
      sodipodi:cx="100.00000"
+
      id="path6318"
+
      sodipodi:type="arc" />
+
    <path
+
      sodipodi:type="arc"
+
      id="path6320"
+
      sodipodi:cx="100.00000"
+
      sodipodi:cy="165.08202"
+
      sodipodi:rx="10.000000"
+
      sodipodi:ry="8.2801600"
+
      d="M 110.00000 165.08202 A 10.000000 8.2801600 0 1 1  90.000000,165.08202 A 10.000000 8.2801600 0 1 1  110.00000 165.08202 z"
+
      transform="matrix(0.285714,0.000000,0.000000,0.316641,181.7008,47.94136)"
+
      style="fill:#8093e2;fill-opacity:1.0000000;stroke:#0a0a0a;stroke-opacity:1.0000000" />
+
    <path
+
      style="fill:#8093e2;fill-opacity:1.0000000;stroke:#0a0a0a;stroke-opacity:1.0000000"
+
      transform="matrix(0.285714,0.000000,0.000000,0.316641,199.6656,37.51016)"
+
      d="M 110.00000 165.08202 A 10.000000 8.2801600 0 1 1  90.000000,165.08202 A 10.000000 8.2801600 0 1 1  110.00000 165.08202 z"
+
      sodipodi:ry="8.2801600"
+
      sodipodi:rx="10.000000"
+
      sodipodi:cy="165.08202"
+
      sodipodi:cx="100.00000"
+
      id="path6322"
+
      sodipodi:type="arc" />
+
    <path
+
      sodipodi:type="arc"
+
      id="path6324"
+
      sodipodi:cx="100.00000"
+
      sodipodi:cy="165.08202"
+
      sodipodi:rx="10.000000"
+
      sodipodi:ry="8.2801600"
+
      d="M 110.00000 165.08202 A 10.000000 8.2801600 0 1 1  90.000000,165.08202 A 10.000000 8.2801600 0 1 1  110.00000 165.08202 z"
+
      transform="matrix(0.285714,0.000000,0.000000,0.316641,194.3230,58.37246)"
+
      style="fill:#8093e2;fill-opacity:1.0000000;stroke:#0a0a0a;stroke-opacity:1.0000000" />
+
    <path
+
      style="fill:#8093e2;fill-opacity:1.0000000;stroke:#0a0a0a;stroke-opacity:1.0000000"
+
      transform="matrix(0.285714,0.000000,0.000000,0.316641,207.2771,47.94136)"
+
      d="M 110.00000 165.08202 A 10.000000 8.2801600 0 1 1  90.000000,165.08202 A 10.000000 8.2801600 0 1 1  110.00000 165.08202 z"
+
      sodipodi:ry="8.2801600"
+
      sodipodi:rx="10.000000"
+
      sodipodi:cy="165.08202"
+
      sodipodi:cx="100.00000"
+
      id="path6326"
+
      sodipodi:type="arc" />
+
    <path
+
      sodipodi:type="arc"
+
      id="path6328"
+
      sodipodi:cx="100.00000"
+
      sodipodi:cy="165.08202"
+
      sodipodi:rx="10.000000"
+
      sodipodi:ry="8.2801600"
+
      d="M 110.00000 165.08202 A 10.000000 8.2801600 0 1 1  90.000000,165.08202 A 10.000000 8.2801600 0 1 1  110.00000 165.08202 z"
+
      transform="matrix(0.285714,0.000000,0.000000,0.316641,204.8812,21.86343)"
+
      style="fill:#8093e2;fill-opacity:1.0000000;stroke:#0a0a0a;stroke-opacity:1.0000000" />
+
    <path
+
      sodipodi:nodetypes="cs"
+
      id="path6330"
+
      d="M 202.20275,80.838333 C 209.90845,78.424023 207.58918,79.024993 209.51028,78.543423"
+
      style="fill:none;fill-opacity:0.75000000;fill-rule:evenodd;stroke:#000000;stroke-width:0.049456649;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4.0000000;stroke-dasharray:0.098913291 0.049456646 ;stroke-dashoffset:0.00000000;stroke-opacity:1.0000000" />
+
    <path
+
      style="fill:none;fill-opacity:0.75000000;fill-rule:evenodd;stroke:#000000;stroke-width:0.070179656;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4.0000000;stroke-dasharray:0.14035930 0.070179651 ;stroke-dashoffset:0.00000000;stroke-opacity:1.0000000"
+
      d="M 214.43578,77.361283 C 229.95197,74.946973 225.28189,75.547943 229.15022,75.066373"
+
      id="path7076"
+
      sodipodi:nodetypes="cs" />
+
    <path
+
      sodipodi:nodetypes="cs"
+
      id="path7078"
+
      d="M 216.56965,80.735263 C 224.23717,88.841753 221.92939,86.823883 223.84098,88.440843"
+
      style="fill:none;fill-opacity:0.75000000;fill-rule:evenodd;stroke:#000000;stroke-width:0.090399556;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4.0000000;stroke-dasharray:0.18079909 0.090399546 ;stroke-dashoffset:0.00000000;stroke-opacity:1.0000000" />
+
    <path
+
      style="fill:none;fill-opacity:0.75000000;fill-rule:evenodd;stroke:#000000;stroke-width:0.062721848;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4.0000000;stroke-dasharray:0.12544369 0.062721845 ;stroke-dashoffset:0.00000000;stroke-opacity:1.0000000"
+
      d="M 228.95806,92.432483 C 234.20881,98.131133 232.62844,96.712623 233.93750,97.849303"
+
      id="path7080"
+
      sodipodi:nodetypes="cs" />
+
    <path
+
      style="fill:none;fill-opacity:0.75000000;fill-rule:evenodd;stroke:#000000;stroke-width:0.10834553;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4.0000000;stroke-dasharray:0.21669104 0.10834552 ;stroke-dashoffset:0.00000000;stroke-opacity:1.0000000"
+
      d="M 201.57555,85.440843 C 208.64032,98.078873 206.51395,94.933013 208.27527,97.453853"
+
      id="path7082"
+
      sodipodi:nodetypes="cs" />
+
    <path
+
      sodipodi:nodetypes="cs"
+
      id="path7084"
+
      d="M 210.30308,102.79327 C 221.31246,108.79411 217.99883,107.30038 220.74358,108.49733"
+
      style="fill:none;fill-opacity:0.75000000;fill-rule:evenodd;stroke:#000000;stroke-width:0.093198687;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4.0000000;stroke-dasharray:0.18639735 0.093198674 ;stroke-dashoffset:0.00000000;stroke-opacity:1.0000000" />
+
    <path
+
      style="fill:none;fill-opacity:0.75000000;fill-rule:evenodd;stroke:#000000;stroke-width:0.0098194452;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4.0000000;stroke-dasharray:0.019638886 0.0098194435 ;stroke-dashoffset:0.00000000;stroke-opacity:1.0000000"
+
      d="M 225.99811,110.84425 C 246.96509,110.87923 240.65440,110.87053 245.88168,110.87750"
+
      id="path7086"
+
      sodipodi:nodetypes="cs" />
+
    <path
+
      sodipodi:nodetypes="cs"
+
      id="path7088"
+
      d="M 196.81202,112.27357 C 208.06273,100.94546 204.67646,103.76290 207.48138,101.50570"
+
      style="fill:none;fill-opacity:0.75000000;fill-rule:evenodd;stroke:#000000;stroke-width:0.12944280;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4.0000000;stroke-dasharray:0.25888552 0.12944277 ;stroke-dashoffset:0.00000000;stroke-opacity:1.0000000" />
+
    <path
+
      style="fill:none;fill-opacity:0.75000000;fill-rule:evenodd;stroke:#000000;stroke-width:0.031499755;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4.0000000;stroke-dasharray:0.062999488 0.031499747 ;stroke-dashoffset:0.00000000;stroke-opacity:1.0000000"
+
      d="M 199.83624,72.984023 C 199.01175,82.138113 199.25991,79.861383 199.05436,81.685393"
+
      id="path7090"
+
      sodipodi:nodetypes="cs" />
+
    <path
+
      sodipodi:nodetypes="cs"
+
      id="path7092"
+
      d="M 236.12654,75.043253 C 251.64273,72.628943 246.97265,73.229913 250.84098,72.748343"
+
      style="fill:none;fill-opacity:0.75000000;fill-rule:evenodd;stroke:#000000;stroke-width:0.070179656;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow2Mend);stroke-miterlimit:4.0000000;stroke-dasharray:0.14035930 0.070179651 ;stroke-dashoffset:0.00000000;stroke-opacity:1.0000000" />
+
    <g
+
      id="g9474"
+
      transform="matrix(0.465744,0.000000,0.000000,0.426414,155.9561,38.18866)">
+
      <path
+
        d="M 264.83163,74.071413 C 264.73021,72.462969 264.98848,70.919635 265.41417,69.378711 C 266.30943,66.976094 268.22386,65.223009 270.74161,65.970072 C 272.33572,68.486680 271.63088,71.555687 270.81649,74.261243 C 269.89972,76.570876 269.31914,78.842428 269.58066,81.287404 C 271.90312,83.104607 271.71536,82.314146 273.13426,80.703982 C 275.16142,78.594399 275.23657,76.437259 274.71229,73.750189 C 274.01449,71.785356 273.97259,70.062468 275.00892,68.322499 C 277.25388,66.627980 279.73329,66.935242 282.37745,66.942144 L 281.16795,67.820223 C 279.53885,67.814170 274.70661,68.134667 276.39905,67.755928 C 275.27242,69.410737 275.34766,71.108445 276.02612,73.049263 C 276.56472,75.754796 276.53538,77.983274 274.49670,80.122909 C 272.90976,81.979540 270.18331,84.469023 268.26711,82.007964 C 267.82612,79.547150 268.64051,77.213254 269.48012,74.892427 C 270.28467,72.264562 271.02454,69.231946 269.48088,66.776862 C 267.32211,66.280915 268.49987,65.760812 266.76828,68.745848 C 266.32524,70.263995 266.05830,71.790054 266.18500,73.381835 L 264.83163,74.071413 z "
+
        id="path8661"
+
        style="fill:#000000;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
      <path
+
        d="M 282.79836,77.265498 C 284.62115,75.778651 286.80891,76.173462 289.06222,76.009428 C 291.44542,75.960984 293.75797,75.490826 296.07676,75.057929 C 295.29056,76.183492 293.29239,76.901192 291.78137,77.465892 C 290.29902,78.269702 287.39580,79.340252 290.96945,77.388504 C 294.80229,75.808049 293.67301,76.192569 294.87870,75.334315 C 295.07841,73.742673 293.59904,73.875343 292.12955,73.560192 C 291.34335,73.535293 290.58614,73.350648 289.81609,73.223522 L 291.05171,72.369777 C 291.81786,72.490468 292.57566,72.659342 293.35481,72.701225 C 294.90560,73.031036 296.48597,72.980153 296.26927,74.761760 C 293.86373,76.393857 293.60422,76.775807 289.78647,78.317852 C 290.74592,77.574806 291.84392,77.009504 292.96144,76.536404 C 294.07714,76.110602 296.96255,74.845321 294.85560,75.947282 C 292.54369,76.422813 290.24182,76.810707 287.87056,76.896461 C 286.61802,76.978523 281.74770,77.471774 284.15173,76.575920 L 282.79836,77.265498 z "
+
        id="path8663"
+
        style="fill:#000000;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
      <path
+
        d="M 302.51772,65.891400 C 302.03167,67.734789 302.43738,69.698987 302.88560,71.520949 C 304.99566,73.494558 304.52693,72.725250 306.09452,70.242282 C 305.61730,68.846749 308.66417,64.621011 307.77971,67.505545 C 307.03125,70.858280 306.34011,74.236623 305.39665,77.540814 C 304.56651,80.929602 303.10439,82.563910 300.08144,84.065508 C 297.32440,84.287999 297.72359,82.602965 299.11429,80.956353 C 303.09784,77.586789 305.29399,76.690129 308.19689,75.030045 C 308.10311,75.085370 308.38659,74.923110 308.48145,74.869643 L 309.86958,74.332125 C 304.20550,77.658392 313.02988,72.468286 307.04870,75.957408 C 306.42006,76.320221 303.68908,77.567388 300.49284,80.387754 C 299.14646,81.909046 298.57781,83.469090 301.26911,83.153312 C 302.65562,81.846381 303.32026,79.921577 304.06625,78.168300 C 305.03069,74.877904 305.70322,71.499836 306.43167,68.151129 C 307.32995,64.616336 309.31964,67.260662 307.44989,69.632210 C 306.26212,71.577024 303.51390,75.078617 301.58411,72.241935 C 301.12744,70.419636 300.69707,68.416548 301.16435,66.580978 L 302.51772,65.891400 z "
+
        id="path8665"
+
        style="fill:#000000;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
      <path
+
        d="M 264.18870,61.100272 C 263.24282,62.154286 262.51905,63.268849 261.96491,64.598871 C 261.04786,67.525358 260.93680,70.636241 261.15238,73.676940 C 261.22538,76.540709 262.31041,79.100850 263.55097,81.620904 C 264.18375,82.817366 265.02679,83.870512 265.93530,84.844245 L 264.66469,85.649333 C 263.75197,84.643928 262.89490,83.575209 262.25549,82.356772 C 261.01098,79.816703 259.91715,77.239141 259.84703,74.354484 C 259.62486,71.298279 259.72734,68.178294 260.60783,65.225986 C 261.13834,63.916194 261.75861,62.700727 262.83533,61.789850 L 264.18870,61.100272 z "
+
        id="path8667"
+
        style="fill:#000000;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
      <path
+
        d="M 309.32323,57.854489 C 310.34607,59.416689 311.45177,60.926389 312.50176,62.478052 C 314.38505,65.023928 315.57812,67.904407 315.98060,71.037277 C 316.32411,74.472796 314.52853,77.143240 312.35057,79.598275 C 311.65115,80.424222 310.77499,81.053084 309.91635,81.697311 L 308.52558,82.246056 C 309.39253,81.610832 310.27915,80.990552 310.98727,80.170130 C 313.15630,77.755009 314.98899,75.127958 314.66945,71.722715 C 314.28386,68.607879 313.09720,65.756292 311.22255,63.229682 C 310.17340,61.687258 309.07660,60.184543 308.02922,58.647463 L 309.32323,57.854489 z "
+
        id="path8669"
+
        style="fill:#000000;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
      <path
+
        d="M 313.68251,56.159774 C 314.71407,57.347830 315.93208,58.264521 317.26262,59.058908 L 316.01971,59.902781 C 314.71764,59.091974 313.51594,58.160262 312.45367,57.052576 L 313.68251,56.159774 z "
+
        id="path8671"
+
        style="fill:#000000;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
      <path
+
        d="M 317.29036,55.909884 C 316.58511,57.483665 315.48201,58.835241 314.41823,60.181119 L 313.04301,60.757719 C 314.10706,59.439751 315.14919,58.107792 315.93699,56.599462 L 317.29036,55.909884 z "
+
        id="path8673"
+
        style="fill:#000000;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
      <path
+
        d="M 315.29406,55.510624 C 315.50126,56.599450 315.32184,57.836042 315.29146,58.976149 L 313.95721,59.653661 C 313.98414,58.524036 314.17872,57.262553 313.94069,56.200201 L 315.29406,55.510624 z "
+
        id="path8675"
+
        style="fill:#000000;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
      <path
+
        d="M 313.31584,57.854489 C 314.33492,58.637048 315.52116,58.440527 316.73855,58.391667 L 315.52285,59.264383 C 314.25671,59.324339 313.07137,59.486207 312.02182,58.647463 L 313.31584,57.854489 z "
+
        id="path8677"
+
        style="fill:#000000;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
    </g>
+
    <g
+
      id="g9464"
+
      transform="matrix(0.686164,0.000000,0.000000,0.585933,111.4012,9.904443)">
+
      <path
+
        d="M 350.81375,110.45922 C 348.60511,112.23427 349.88516,108.54589 350.26734,107.31259 C 352.68402,104.93835 354.06037,105.39317 354.33858,108.53212 C 353.92995,111.16018 353.49845,113.62174 354.15012,116.20314 C 355.96310,117.57670 355.09986,117.70774 355.45179,115.03563 C 355.43035,112.82687 355.26333,110.84958 356.43266,108.97798 C 357.94699,107.61619 359.21691,107.41896 361.05912,107.56748 L 359.84130,108.43676 C 357.49184,108.31713 358.18305,108.18830 357.82059,108.40996 C 356.56437,110.21505 356.75618,112.16845 356.78384,114.36825 C 356.54852,116.41833 354.64928,119.28320 352.84555,116.94290 C 352.18463,114.33731 352.57281,111.85715 353.01246,109.20375 C 352.84784,107.18413 351.40471,105.23689 351.63161,106.68416 C 351.01408,108.56557 351.59996,110.52202 349.58491,111.35202 L 350.81375,110.45922 z "
+
        id="path8679"
+
        style="fill:#000000;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
      <path
+
        d="M 364.38861,111.65700 C 366.29964,111.73404 368.18410,111.63471 370.07552,111.37054 C 371.79358,110.34188 374.28633,111.32935 374.31172,111.33815 C 373.34593,112.41014 372.18285,113.48169 370.78856,113.85299 C 372.77554,112.70522 373.85141,111.60576 372.57882,109.48649 C 372.33617,109.12924 371.89215,109.04598 371.55771,108.83144 L 372.80473,108.00527 C 373.15091,108.23899 373.60914,108.34343 373.86022,108.71789 C 375.15720,110.87699 374.29095,112.11095 372.19037,113.30483 C 369.59183,114.57094 371.71067,113.42404 372.92886,111.93373 C 371.57979,111.89136 370.20036,111.92504 368.89278,112.25975 C 366.98585,112.51946 365.08467,112.59952 363.15977,112.54980 L 364.38861,111.65700 z "
+
        id="path8681"
+
        style="fill:#000000;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
      <path
+
        d="M 377.02387,106.41152 C 377.79273,104.56179 379.19262,103.84622 380.87327,104.70092 C 382.12125,106.53882 381.95442,108.66306 381.83942,110.77610 C 381.98972,111.61383 382.03580,112.47930 382.30567,113.28649 C 383.67936,111.80961 383.77719,110.04150 383.78492,108.13338 C 383.80340,105.73535 385.90573,104.89103 386.33400,107.67989 C 386.25890,109.57368 386.19089,111.02740 387.40720,112.15167 C 386.88711,113.54845 387.96658,109.24201 387.93242,107.46218 C 388.04613,104.82321 388.23528,104.18047 390.70390,102.96156 L 389.51216,103.87408 C 389.45169,104.84818 389.44148,105.83168 389.26505,106.79158 C 389.30610,109.69401 389.24192,111.78833 386.19014,113.03858 C 384.91828,111.75433 384.88486,110.37516 385.00393,108.36827 C 384.74895,106.60096 384.75732,104.98633 385.11040,107.43936 C 385.15770,109.37282 385.00985,111.18360 383.69497,112.71730 C 381.09234,114.38266 380.54300,114.53139 380.51025,111.45545 C 380.61637,109.38082 380.82056,107.28148 379.58712,105.47562 C 377.72934,104.68786 379.90193,103.80067 378.37724,105.72195 L 377.02387,106.41152 z "
+
        id="path8683"
+
        style="fill:#000000;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
      <path
+
        d="M 349.23121,101.82486 C 348.05337,103.69965 347.60150,105.79317 347.34809,107.97299 C 347.08374,112.49721 348.66295,115.66199 352.84095,117.43839 C 353.71080,117.77434 354.63019,117.74439 355.53878,117.82164 L 354.34943,118.67638 C 353.43291,118.58603 352.50412,118.60390 351.62890,118.25622 C 347.41188,116.41955 345.79492,113.21840 346.03033,108.62883 C 346.26602,106.47337 346.62528,104.33618 347.87784,102.51443 L 349.23121,101.82486 z "
+
        id="path8685"
+
        style="fill:#000000;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
      <path
+
        d="M 389.81472,93.784554 C 391.52423,92.513138 391.73154,96.513495 392.71618,98.383715 C 394.86355,102.11084 396.00411,106.40735 394.96321,110.64012 C 394.70148,111.69726 393.96016,112.27896 393.25803,112.99532 L 391.86916,113.54019 C 392.59843,112.85755 393.35105,112.32579 393.63072,111.26819 C 394.73697,107.07808 393.57835,102.80743 391.43549,99.117669 C 390.36855,97.111984 388.27172,94.098562 391.04355,92.891752 L 389.81472,93.784554 z "
+
        id="path8687"
+
        style="fill:#000000;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
      <path
+
        d="M 396.74323,93.839644 C 397.25742,95.280108 398.79957,96.037656 399.98057,96.947563 L 398.70989,97.741192 C 397.48767,96.799693 395.93568,96.021243 395.38986,94.529222 L 396.74323,93.839644 z "
+
        id="path8689"
+
        style="fill:#000000;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
      <path
+
        d="M 400.71246,93.894041 C 399.36387,94.927540 398.13222,96.108225 396.84427,97.211468 L 395.45768,97.758251 C 396.75088,96.681071 397.96161,95.487568 399.31032,94.474824 L 400.71246,93.894041 z "
+
        id="path8691"
+
        style="fill:#000000;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
      <path
+
        d="M 398.73953,92.641862 C 398.69898,94.204309 398.41653,95.765084 398.05843,97.284348 L 396.70282,97.922125 C 397.05592,96.421106 397.37467,94.879450 397.38616,93.331440 L 398.73953,92.641862 z "
+
        id="path8693"
+
        style="fill:#000000;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
    </g>
+
    <g
+
      id="g9455"
+
      transform="matrix(0.669616,0.000000,0.000000,0.712161,106.5631,-29.63696)">
+
      <path
+
        d="M 299.16805,211.01781 C 299.05551,209.36712 299.59149,207.89286 300.24236,206.41060 C 302.85489,203.69744 304.58959,204.94388 304.62389,208.18011 C 304.23193,210.64280 303.20157,212.90411 303.52549,215.41385 C 305.84246,216.86017 304.91616,216.54190 305.85795,214.69904 C 306.54290,212.82344 306.11343,210.83940 305.84261,208.92250 C 306.34677,206.34697 309.86031,205.79588 312.11076,205.11694 C 312.27084,205.07398 312.43092,205.03102 312.59100,204.98806 L 311.40907,205.89579 C 311.25051,205.93968 311.09195,205.98356 310.93339,206.02744 C 307.55235,207.05227 307.98110,206.08451 307.17376,208.23006 C 307.43998,210.16271 307.86711,212.17101 307.21473,214.06865 C 306.28716,216.03199 303.95140,218.27245 302.21056,216.12946 C 301.85780,213.60200 302.85458,211.32539 303.29463,208.85158 C 303.28918,206.67320 301.43658,204.31261 301.60179,205.80022 C 300.94484,207.25411 300.39294,208.69949 300.52142,210.32823 L 299.16805,211.01781 z "
+
        id="path8695"
+
        style="fill:#5d05ca;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
      <path
+
        d="M 316.07807,210.27438 C 317.77412,210.35097 319.44502,210.24299 321.12608,210.03767 C 322.41274,210.01097 329.62822,208.35077 325.77982,210.49876 C 321.50152,211.85053 323.40338,211.38026 321.35162,212.19945 C 324.15394,209.87657 322.40486,212.89877 325.54480,209.15330 C 324.76706,207.63657 322.88070,207.91886 321.28787,208.08029 C 321.18568,208.10493 321.08348,208.12958 320.98128,208.15422 L 322.17655,207.24486 C 322.27884,207.22366 322.38112,207.20246 322.48340,207.18125 C 324.23243,207.03824 326.09282,206.80261 326.90501,208.51383 C 324.43925,211.83362 321.02395,212.17572 322.75590,211.61480 C 319.67990,212.86877 323.74915,210.40575 326.96723,209.56499 C 325.12358,210.67907 322.50339,210.49411 319.93380,210.92289 C 318.24068,211.13445 316.55691,211.21813 314.84924,211.16718 L 316.07807,210.27438 z "
+
        id="path8697"
+
        style="fill:#5d05ca;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
      <path
+
        d="M 330.86523,200.84149 C 330.90168,202.68827 331.32830,204.49627 331.99144,206.20289 C 333.63541,207.22910 333.35434,206.30471 334.45597,203.24564 C 336.78874,199.09310 336.27986,203.79497 335.99935,206.08841 C 335.60759,209.85261 334.98285,213.73454 332.16208,216.41028 C 328.63768,218.58103 328.66563,215.67702 330.38931,213.64209 C 331.47114,212.48790 332.82786,211.66132 334.15331,210.82275 L 335.54399,210.28887 C 334.21288,211.11305 332.85183,211.93201 331.75963,213.07120 C 329.96420,215.10565 330.90911,216.20498 330.77248,216.95254 C 333.68710,214.39066 334.29540,210.47799 334.68553,206.73826 C 334.84885,205.37062 335.37432,199.56907 335.80294,202.60562 C 335.02581,204.82085 333.45933,208.61074 330.69529,206.94681 C 330.02225,205.21958 329.59730,203.39642 329.51185,201.53107 L 330.86523,200.84149 z "
+
        id="path8699"
+
        style="fill:#5d05ca;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
      <path
+
        d="M 300.92068,199.24445 C 299.66678,200.62538 298.89555,202.28327 298.28761,204.04728 C 297.16125,207.79327 296.71709,211.84681 299.49402,214.91018 C 300.74107,216.07357 302.23407,216.59998 303.84475,216.93881 L 302.62822,217.80858 C 301.00493,217.41938 299.48949,216.86257 298.23525,215.68036 C 295.44316,212.56639 295.83169,208.48795 296.95229,204.67791 C 297.53231,202.94317 298.20132,201.18677 299.56731,199.93403 L 300.92068,199.24445 z "
+
        id="path8701"
+
        style="fill:#5d05ca;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
      <path
+
        d="M 337.23889,194.30395 C 338.73807,195.89240 340.03070,197.66056 341.01991,199.60661 C 342.82632,203.61220 341.56159,207.05743 339.55376,210.62623 C 339.30799,211.00528 339.17379,211.43645 338.98380,211.84156 L 337.63879,212.46035 C 337.65873,212.41700 338.14418,211.21285 338.20637,211.22611 C 340.20399,207.70254 341.54279,204.31117 339.73824,200.33392 C 338.77312,198.44544 337.50874,196.68462 336.01005,195.19675 L 337.23889,194.30395 z "
+
        id="path8703"
+
        style="fill:#5d05ca;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
      <path
+
        d="M 345.23861,188.46441 C 345.11700,190.21428 345.20335,191.97393 345.22122,193.72956 C 345.22388,194.03627 345.22441,194.34300 345.22601,194.64972 L 343.89585,195.32799 C 343.89506,195.02106 343.89523,194.71414 343.89346,194.40721 C 343.87767,192.65555 343.78951,190.89807 343.88524,189.15399 L 345.23861,188.46441 z "
+
        id="path8705"
+
        style="fill:#5d05ca;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
      <path
+
        d="M 344.82484,197.49804 C 344.40695,197.72395 343.17783,198.44211 343.57118,198.17576 C 347.31488,195.64077 342.04350,199.66344 345.33723,197.91359 C 345.30590,198.04314 342.58134,199.44339 345.44701,198.02393 L 344.13555,198.79099 C 347.00160,196.73873 344.71120,199.11408 343.93292,198.48217 C 344.45296,198.18623 345.30436,197.34197 345.61437,197.85374 C 346.04874,198.57081 342.77272,198.47461 343.59600,198.39084 L 344.82484,197.49804 z "
+
        id="path8707"
+
        style="fill:#5d05ca;fill-opacity:1.0000000;fill-rule:nonzero;stroke:none;stroke-width:1.0000000px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000" />
+
    </g>
+
  </g>
+
</svg>
+
</pic-svg>
+
 
+
 
+
[[Category:Алгоритмы|Д]]
+
 
+
{{replicate-from-custiswiki-to-lib}}
+

Текущая версия на 20:43, 13 июня 2011

  1. REDIRECT discopal:Алгоритм Дейкстры