Quelltext der Seite Graph Theory and Algorithms

<span id="graph-theory-and-algorithms"></span>
= Graph Theory and Algorithms =

For a comprehensive subject on graph theory the reader is referred to the book [Gross and Yellen(1998)].

<span id="seven-bridges-of-königsberg"></span>
== Seven Bridges of Königsberg ==

Seven Bridges of Königsberg is a problem of mathematics formulated by Leonhard Euler after a walk in Königsberg in Prussia (now Kaliningrad, Russia). The islands were connected to each other and the mainlands on the two sides of the Pregel River via seven bridges (see Figure [[#fig:Königsberg_bridges|2]]).

<div id="fig:Königsberg_bridges" class="figure">

[[Datei:Konigsberg_bridges_2L.png|460px|thumb|center|Figure 2: Map of Königsberg with the seven bridges in the 18-th century (Source: By Bogdan Giuşcă - Public domain (PD),based on the image, CC BY-SA 3.0, \url{https://commons.wikimedia.org/w/index.php?curid=112920})]]


</div>
The problem is to find a walk path that would cross each of the seven bridges only once.

Leonhard Euler has resolved the problem in 1736 by showing that such a walk path does not exist. His solution founded the graph theory and therefore the Seven Bridges of Königsberg problem is considered to be the first problem of graph theory.

<span id="graphs-theory-basics"></span>
== Graphs theory basics ==

A graph is a mathematical object consisting of vertices (nodes) and edges connecting pairs of vertices, see example in Figure [[#fig:exa_undirected_graph|3]].

<div id="fig:exa_undirected_graph" class="figure">

[[Datei:exa_undirected_graph.jpg|460px|thumb|center|Figure 3: Example of an undirected graph]]

</div>
Graph theory studies properties of graphs and problems which can be described by means of graphs. Graph theoretical algorithms and results are applied in many areas, like e.g. transport networks, computer science or biology.

<span id="basics"></span>
=== Basics ===

<span>'''<math display="inline">\mathrm{\ \ \ \ }</math> Basic terms'''</span>

A graph is composed of vertices (nodes) and edges connecting pairs of vertices. Vertex and edge are the two basic units of the graph. The set of vertices and edges is denoted by <math display="inline">\mathcal{V}</math> and <math display="inline">\mathcal{E}</math>, respectively. In undirected graph the edges have no direction, they simple connect two vertices. The graph shown in Figure [[#fig:exa_undirected_graph|3]] is an example of an undirected graph.

The degree of a vertex is the number of edges connected to it. A path is an uninterrupted line connecting two vertices over sequence of edges and vertices. For example the path <math display="inline">(1,2,5,6)</math> in Figure [[#fig:exa_undirected_graph|3]] connects the vertices <math display="inline">1</math> and <math display="inline">6</math>. This way a path is specified by an ordered list of all vertices locating on the uninterrupted line going from the starting vertex of the path to the end vertex of it. A cycle is a path, whose start vertex and end vertex is the same. For example <math display="inline">(1,2,3,4,1)</math> in Figure [[#fig:exa_undirected_graph|3]] is a cycle. A graph is called connected graph, if there is a path between any two vertices of the graph. For example the graph in Figure [[#fig:exa_undirected_graph|3]] is a connected graph.

In the weighted graph each edge has a weight (or cost) associated to them. This weight can represent different physical properties, like e.g. distance between two nodes, capacity of a network link, transport cost of a way between two nodes, etc. An example of a weighted graph can be seen in Figure [[#fig:exa_weighted_graph|4]].

<div id="fig:exa_weighted_graph" class="figure">

[[Datei:exa_weighted_graph.jpg|460px|thumb|center|Figure 4: Example of a weighted graph]]

</div>
<span>'''<math display="inline">\mathrm{\ \ \ \ }</math> Types of graphs'''</span>

The classification of graphs into various types is based on the properties of the considered subclass of graphs. The most important types of graphs together with their definitions are given as follows.

* Undirected graph - A graph with edges having no direction.
* Directed graph - A graph with edges having direction.
* Unweighted graph - A graph with edges having no weights associated to them.
* Weighted graph - A graph with edges having weights associated to them.
* Connected graph - A graph having path between any two of its vertices.
* Disconnected graph - A graph containing at least one pair of vertices having no path between them.
* Cyclic graph - A graph containing at least one cycle.
* Acyclic graph - A graph does not containing any cycles.
* Tree - A connected acyclic graph.
* Multi-graph - A graph containing at least one pair of vertices having multiple edges between them.
* Simple graph - A graph without cycles and multiple edges between the same pair of vertices.
* Complete graph - A graph in which each pair of vertices is connected by edge.

<span>'''<math display="inline">\mathrm{\ \ \ \ }</math> Graph descriptions'''</span>

The most often used graph representations in algorithms are

* adjacency matrix and
* adjacency list,

because they enable the mathematical description of graphs by means of programming variables, like matrix, array and list.

<span>'''''<math display="inline">\mathrm{\ \ \ \ \ \ }</math> Adjacency matrix'''''</span>

Adjacency matrix is suitable to describe unweighted graphs, both undirected and directed ones. Adjacency matrix is a <math display="inline">V \times V</math> matrix, whose <math display="inline">(i,j)</math>-th element describes the existence of the connection from vertex <math display="inline">i</math> to vertex <math display="inline">j</math> as a binary value. If there is a connection then this value equals <math display="inline">1</math>, otherwise <math display="inline">0</math>. For example the adjacency matrix of the undirected, unweighted graph example in Figure [[#fig:exa_undirected_graph|3]] looks like

<math display="block">\begin{aligned}
    \left(
    \begin{array}{llllll}
    0 & 1 & 0 & 1 & 0 & 0\\
    1 & 0 & 1 & 0 & 1 & 0\\
    0 & 1 & 0 & 1 & 0 & 0\\
    1 & 0 & 1 & 0 & 1 & 0\\
    0 & 1 & 0 & 1 & 0 & 1\\
    0 & 0 & 0 & 0 & 1 & 0
    \end{array}
    \right).
\end{aligned}</math>

The construction of the adjacency matrix implies that the adjacency matrix of an undirected graph is always a symmetric matrix. The idea of describing an unweighted graph by constructing an adjacency matrix as 2-dimensional array can be theoretically extended to describe a weighted graph by constructing a 3-dimensional array, in which the third dimension represents the weight assigned to the edge specified by the first two dimensions. Such a 3-dimensional could be called as adjacency tensor.

<span>'''''<math display="inline">\mathrm{\ \ \ \ \ \ }</math> Adjacency list'''''</span>

Another way of mathematical representation of a graph is the adjacency list. Adjacency list is an array of lists, in which each list specifies a set of neighbours of a vertex assigned to the actual list as index of the array. In describing a weighted graph, the list consists of the comma separated sequence of &quot;ending vertex: weight&quot; pairs, where each such pair specifies an edge to the given ending vertex with the given weight starting from the vertex to which the considered list belongs to. In case of an unweighted graph the list is a comma separated sequence of neighbour vertexes of the vertex to which the considered list belongs to. Therefore this type of representation is suitable to describe both unweighted and weighted graphs. For example the adjacency list of the unweighted graph example in Figure [[#fig:exa_undirected_graph|3]] is given as

<math display="block">\begin{aligned}
\begin{array}{ll}
1: & \{2,4\} \\
2: & \{1,3,5\}\\
3: & \{2,4\} \\
4: & \{1,3,5\} \\
5: & \{2,4,6\} \\
6: & \{5\}
\end{array}.
\end{aligned}</math>

Similarly the adjacency list of the weighted graph example in Figure [[#fig:exa_weighted_graph|4]] can be given as

<math display="block">\begin{aligned}
\begin{array}{ll}
1: & \{2:5,3:2\} \\
2: & \{1:5,3:3,4:4\}\\
3: & \{1:2,2:3,4:1\} \\
4: & \{2:4,3:1,5:3\} \\
5: & \{1:8,4:3\} 
\end{array}.
\end{aligned}</math>

<span>'''''<math display="inline">\mathrm{\ \ \ \ \ \ }</math> Edge list'''''</span>

Still another way of mathematically describing a graph is to specify it as edge list. Each edge is specified by a sequence in the form <math display="inline">[</math> starting vertex, ending vertex, weight (optional) <math display="inline">]</math>. Thus the edge list can be given as a two/three column matrix for unweighted/weighted graphs. Hence this type of representation is suitable to describe both unweighted and weighted graphs. The unweighted graph in Figure [[#fig:exa_undirected_graph|3]] and the weighted graph in Figure [[#fig:exa_weighted_graph|4]] can be described by edge list, respectively, as

<math display="block">\begin{aligned}
&&[ [1,2], [2,3], [1,4], [4,5], [2,5], [3,4], [5,6] ]  \\
&&[ [1,2,5], [2,3,3], [3,1,2], [2,4,4], [4,3,1], [1,5,8], [4,5,3] ]. 
\end{aligned}</math>

<span id="graph-problems"></span>
=== Graph problems ===

Graph theory can be applied for solving different problems in many areas. Without claim for completeness we list several well-known graph problems with their brief description.

* Graph coloring - Graph coloring is a group of problems all of them having something to do with coloring of graphs. Usually they are specified by means of a restriction on the way of coloring, like e.g no adjacent vertices may have the same color. One of the famous result in graph coloring is the so called [https://en.wikipedia.org/wiki/Four_color_theorem Four-color theorem]
* Network flow problems - Network flow problems deal with question related to [https://en.wikipedia.org/wiki/Flow_network Flow networks].
* Covering problems - Covering problems are set cover problems dealing with covering some subsets of vertices/subgraphs. Vertex cover problem is a special case of set cover problems, in which for every edge its starting or end vertex is in the vertex cover.
* Route problems - Route problems are graph problems, which are all related to find a route specified by various constraints on the graph.

<span>'''<math display="inline">\mathrm{\ \ \ \ }</math> Route problems'''</span><br />
Route problems form an important class of graph problems, since they have applications in many areas. Here is a list of several selected Route problems, which will be discussed in more details in the rest of this section.

# Hamiltonian path and Eulerian path
# Traveling salesman problem
# Chinese postman problem (Route inspection problem)
# Minimum spanning tree
# Shortest path problem

<span id="minimum-vertex-cover-problem"></span>
== Minimum Vertex Cover Problem  ==

Vertex cover problem is a kind of set cover problems, in which a set of vertices are searched, which includes at least one endpoint of every edge of the graph. The Minimum Vertex Cover Problem (MIN-VC) is a vertex cover problem on undirected graph, in which a set of minimum number of vertices are searched, which includes at least one endpoint of every edge of the graph.

<div id="fig:exa_graph_minvc" class="figure">

[[Datei:exa_graph_minvc.jpg|460px|thumb|center|Figure 5: Example graph for MIN-VC problem]]

</div>
For example the minimum vertex cover of the example graph in Figure [[#fig:exa_graph_minvc|5]] is <math display="inline">\{2,3,4\}</math> or <math display="inline">\{2,3,5\}</math> or <math display="inline">\{2,4,5\}</math> or <math display="inline">\{1,3,5\}</math>.

The MIN-VC is an optimization problem and it can be reformulated to a decision problem, which is also called as &quot;vertex cover problem&quot;. It is known to be [https://en.wikipedia.org/wiki/NP-completeness NP-complete] (nondeterministic polynomial-time complete), so usually so it cannot be solved by a polynomial-time algorithm.

There is an approximate algorithm for determining the minimum vertex cover of an undirected graph. Its schematic representation is shown in Algorithm 1.

<br />
Algorithm 1 Approximate algorithm for MIN-VC<br />
<span>'''—————————————————————————————'''</span><br />
Input: Undirected graph given by an edge list (= set <math display="inline">\mathcal{E}</math>).<br />
Output : Found set of vertex cover <math display="inline">\mathcal{C}</math>.<br />
<span>'''—————————————————————————————'''</span><br />
1 Initialise set of vertex cover: <math display="inline">\mathcal{C}</math>=<math display="inline">\{\}</math><br />
2 while <math display="inline">\mathcal{E}</math> is not empty<br />
3   Take an arbitrary edge <math display="inline">(u,v)</math> from set <math display="inline">\mathcal{E}</math><br />
4   Add <math display="inline">u</math> and <math display="inline">v</math> to <math display="inline">\mathcal{C}</math><br />
5   Remove all edges from set <math display="inline">\mathcal{E}</math> having endpoint either <math display="inline">u</math> or <math display="inline">v</math><br />
6 end<br />
<span>'''—————————————————————————————'''</span><br />


It can be proven that the above approximate algorithm for MIN-VC always finds a vertex cover whose size is not more than twice of the size of the minimum vertex cover. The computational complexity of the algorithm is <math display="inline">\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)</math>. The memory need of the algorithm is <math display="inline">\mathcal{O}(|\mathcal{V}|</math> The memory is needed to store the visited vertices, i.e. the set <math display="inline">\mathcal{C}</math>.

<span id="eulerian-path-and-hamiltonian-path"></span>
== Eulerian path and Hamiltonian path ==

<span id="eulerian-path-and-cycle"></span>
=== Eulerian path and cycle ===

<span>'''<math display="inline">\mathrm{\ \ \ \ }</math> Eulerian path'''</span>

Eulerian path in an undirected graph <math display="inline">\boldsymbol{G}</math> is a path that visits every edges of <math display="inline">\boldsymbol{G}</math> exactly once. Note that the undirected graph <math display="inline">\boldsymbol{G}</math> can be unweighted or weighted. However this does not affect the mathematical treatment of Eulerian path, therefore we treat these cases commonly by simple omitting unweighted or weighted characterization of <math display="inline">\boldsymbol{G}</math>.

The necessary and sufficient conditions for for the existence of Eulerian path in the undirected graph <math display="inline">\boldsymbol{G}</math> can be given as

* Every vertices with non-zero degree of <math display="inline">\boldsymbol{G}</math> form a connected graph.
* Either none of the vertices or exactly two vertices of <math display="inline">\boldsymbol{G}</math> have odd degree and all its other vertices have even degree.

Along the Euler path, each time walking through a vertex we walking through two previously unseen edges: one at approaching the vertex and the other at leaving it. On this way the number of edges at each middle vertex (i.e. the vertices except the starting and ending vertices of the path) must be even. The starting and ending vertices of the path are enabled to have odd degree, as the start or finish of the walk goes through on only one edge connected to that vertices. This argument proves the necessity of the condition. It turns out that the condition is also sufficient.

<div id="fig:exa_graph_E-path" class="figure">

[[Datei:exa_graph_E-path.jpg|460px|thumb|center|Figure 6: Example graph with Euler path]]

</div>
For example the example graph in Figure [[#fig:exa_graph_E-path|6]] has an Euler path <math display="inline">(1,3,4,5,2,4)</math>, since only vertices <math display="inline">1</math> and <math display="inline">4</math> have odd degree.

An Euler path can be determined by going through the graph starting from a vertex with odd degree and selecting always previously unseen edges at each vertices. The conditions ensure that this always leads to an Euler path. This process requires the logging of the already visited edges at each vertex. It follows that the computational complexity of finding an Euler path is <math display="inline">\mathcal{O}(|\mathcal{V}|^2</math>

The Seven Bridges of Königsberg is a problem of finding an Euler path. In fact Leonard Euler solved it in 1736 by showing that there is no path that visits every of the seven bridges exactly once. His solution applies the above argument for necessary condition. Euler’s solution of the Königsberg bridge problem is the first theorem of graph theory and laid the foundations of graph theory.

<span>'''<math display="inline">\mathrm{\ \ \ \ }</math> Eulerian cycle'''</span>

Eulerian cycle in an undirected graph <math display="inline">\boldsymbol{G}</math> is a closed path that visits every edges of <math display="inline">\boldsymbol{G}</math> exactly once and returns to the starting vertex. Similarly to Eulerian path, the undirected graph <math display="inline">\boldsymbol{G}</math> can be unweighted or weighted, which does not affect of the mathematical treatment of Eulerian cycle. Hence these cases are treated commonly by simple omitting unweighted or weighted characterization of <math display="inline">\boldsymbol{G}</math>. A graph containing a Eulerian cycle is a Eulerian graph.

The necessary and sufficient conditions for the existence of Eulerian cycle in the undirected graph <math display="inline">\boldsymbol{G}</math> can be formulated as

* Every vertices with non-zero degree of <math display="inline">\boldsymbol{G}</math> form a connected graph.
* Every vertices of <math display="inline">\boldsymbol{G}</math> have even degree.

This can be argumented similarly as in case of Eulerian path. Because in case of Eulerian cycle the path returns to the starting vertex, no odd degree is allowed yet for that vertex.

The example graph in Figure [[#fig:exa_graph_E-path|6]] has no Eulerian cycle, since not every vertices have even degree (vertices <math display="inline">1</math> and <math display="inline">4</math> have odd degree).

<div id="fig:exa_graph_E-cycle" class="figure">

[[Datei:exa_graph_E-cycle.jpg|460px|thumb|center|Figure 7: Example graph with Eulerian cycle]]

</div>
However the in the graph in Figure [[#fig:exa_graph_E-cycle|7]] every vertices have even degree, therefore it has a Eulerian cycle, e.g. (1,3,5,6,7,5,4,3,2,1).

Finding a Eulerian cycle can be completed on the same way as described for Eulerian path, but the visit can start at any vertex, since all vertices have even degree. Like in case of finding an Eulerian path, finding a Eulerian cycle has a computational complexity of <math display="inline">\mathcal{O}(|\mathcal{V}|^2</math>.

<span id="hamiltonian-path-and-cycle"></span>
=== Hamiltonian path and cycle ===

<span>'''<math display="inline">\mathrm{\ \ \ \ }</math> Hamiltonian path'''</span>

Hamiltonian path in an undirected graph <math display="inline">\boldsymbol{G}</math> is a path that goes through every vertex of <math display="inline">\boldsymbol{G}</math> exactly once. The path have not to return to the starting vertex, i.e. Hamiltonian path is an open path. Finding a Hamiltonian path is in general an NP-complete problem.

For example the example graph in Figure [[#fig:exa_undirected_graph|3]] has more Hamiltonian paths: <math display="inline">(3,2,1,4,5,6)</math> or <math display="inline">(1,4,3,2,5,6)</math>.

Hamiltonian path has applications in many fields including

* transportation networks (finding optimal routes),
* circuit design and
* graph theory research.

<span>'''<math display="inline">\mathrm{\ \ \ \ }</math> Hamiltonian cycle'''</span>

Hamiltonian cycle (or Hamiltonian circuit) in an undirected graph <math display="inline">\boldsymbol{G}</math> is a closed path that goes through every vertex of <math display="inline">\boldsymbol{G}</math> exactly once and returns to the starting vertex. A graph containing a Hamiltonian cycle is a Hamiltonian graph, otherwise it is non-Hamiltonian graph. Like in case of finding a Hamiltonian path, finding a Hamiltonian cycle is also an NP-complete problem. Finding a Hamiltonian path is often easier than finding a Hamiltonian cycle.

The example graph in Figure [[#fig:exa_undirected_graph|3]] has no Hamiltonian cycle.

<div id="fig:exa_graph_H_cycle" class="figure">

[[Datei:exa_graph_H_cycle.jpg|460px|thumb|center|Figure 8: Example graph with Hamiltonian cycle]]

</div>
However a slightly different graph in Figure [[#fig:exa_graph_H_cycle|8]] has a Hamiltonian cycle: (5,2,1,4,3,5).

Hamiltonian cycle has applications in many fields including

* computer science,
* logistics and
* network design.

<span>'''<math display="inline">\mathrm{\ \ \ \ }</math> Algorithms for finding Hamiltonian cycle'''</span>

In the next we give a brief description of the following two algorithms for finding Hamiltonian cycle:

* Brute-force search and
* Backtracing algorithm

<span>'''''<math display="inline">\mathrm{\ \ \ \ \ \ }</math> Brute-force search - for finding Hamiltonian cycle'''''</span>

The brute-force search (also called exhaustive search) follows a naive approach and tries all the possible permutations of all the <math display="inline">|V|</math> vertices. This results in <math display="inline">|V|!</math> different sequences of the <math display="inline">|V|</math> vertices, so the computational complexity of this algorithm is <math display="inline">\mathcal{O}(|\mathcal{V}|!)</math>.

<span>'''''<math display="inline">\mathrm{\ \ \ \ \ \ }</math> Backtracing algorithm - for finding Hamiltonian cycle'''''</span>

The idea of Backtracing algorithm is to add iteratively a new vertex to the actual path of subsequence of vertices, which is an adjacent to the last vertex of the actual path and not yet included in that path. After having the path with <math display="inline">|\mathcal{V}|</math> vertices, it is checked whether it composes a cycle or not. If not then change the path by trying systematically all the adjacent vertices at every position in the path backwards, which is called backtracking.

The algorithm can be implemented on elegant way by applying a recursive function call. The pseudo code of the algorithm is given in Algorithm 2.

<br />
Algorithm 2 Backtracing algorithm - for finding Hamiltonian cycle<br />
<span>'''—————————————————————————————'''</span><br />
Input: Undirected graph.<br />
Output:<br />
- true, if Hamiltonian cycle found,<br />
- false, if Hamiltonian cycle exist<br />
<span>'''—————————————————————————————'''</span><br />
1 Initialise path (=sequence of <math display="inline">|\mathcal{V}|</math> vertices)<br />
2 Set <math display="inline">path[0]</math>= first vertex<br />
3 if <math display="inline">try\_next\_vertex\_and\_check\_cycle(1)</math><br />
4   return <math display="inline">true</math> (cycle found)<br />
5 else<br />
6   return <math display="inline">false</math> (cycle not exists)<br />
7 end<br />
<span>'''—————————————————————————————'''</span><br />
Recursive function<br />
bool try_next_vertex_and_check_cycle(path_index k)<br />
Input: next index in the path (=sequence of <math display="inline">|\mathcal{V}|</math> vertices)<br />
Output:<br />
- true, if cycle found,<br />
- false, if backtracking or cycle not exists<br />
<span>'''—————————————————————————————'''</span><br />
1 if <math display="inline">k == |\mathcal{V}|</math><br />
2   if exists edge between last and first vertices of path<br />
3     return <math display="inline">true</math> (cycle found)<br />
4   else<br />
5     return <math display="inline">false</math> (backtracking or cycle not exists)<br />
6 end<br />
7 for <math display="inline">v \in \mathcal{V}</math><br />
8   if <math display="inline">v</math> is adjacent to <math display="inline">path[k-1]</math> (=last vertex in path)<br />
9    and<br />
10  <math display="inline">v</math> is not yet in <math display="inline">path[]</math><br />
11    path[k]=v<br />
12    if <math display="inline">try\_next\_vertex\_and\_check\_cycle(k+1)</math><br />
13      return <math display="inline">true</math><br />
14    end<br />
15    (Backtracking - remove v from path)<br />
16    <math display="inline">path[k] = -1</math><br />
17  end<br />
18 end<br />
19 return false (backtracking or cycle not exists)<br />
<span>'''—————————————————————————————'''</span><br />


In the course of backtracking every neighbours of every vertices can be tried by the algorithm. Therefore its computational complexity is <math display="inline">\mathcal{O}(|\mathcal{V}|!)</math>.

<span id="chinese-postman-problem-route-inspection-problem"></span>
== Chinese postman problem (Route inspection problem) ==

The Chinese postman problem (also called as route inspection problem) is an extension of finding Eulerian cycle in connected and (unweighted or weighted) undirected graphs. The Chinese postman problem is to find shortest path that visits every edge of the connected and undirected graph <math display="inline">\boldsymbol{G}</math> at least once and return to the starting vertex. So the problem is defined on connected graph. The shortest path is defined as the one with minimum number of edges for unweighted graph and as the path with minimum accumulated weights for weighted graph. The solution path of Chinese postman problem is called Chinese postman tour. The Chinese postman problem can be solved in polynomial time.

<span id="solution-for-eulerian-graph"></span>
=== Solution for Eulerian graph ===

If the graph <math display="inline">\boldsymbol{G}</math> contains an Eulerian cycle, then it is also the solution for the Chinese postman problem, since Eulerian cycle has the shortest path (minimum number of edges in unweighted graph and minimum accumulated weights in weighted graph) due to the necessity of visiting all edges at least once.

Therefore the necessary and sufficient condition for the solution for the Chinese postman problem to be the Eulerian cycle is the existence of Eulerian cycle, which can be given as

* Every vertices of <math display="inline">\boldsymbol{G}</math> have even degree.

For example graph in Figure [[#fig:exa_graph_E-cycle|7]] the solution, i.e the Chinese postman tour is the Eulerian cycle, e.g. (1,3,5,6,7,5,4,3,2,1).

<span id="solution-for-non-eulerian-graph"></span>
=== Solution for Non-Eulerian graph ===

If the graph <math display="inline">\boldsymbol{G}</math> has no Eulerian cycle, then the graph must be extended to become Eulerian. This is done by duplicating some edges of <math display="inline">\boldsymbol{G}</math> connected to vertices with odd degree in order to change the degree of all these vertices become to even. The edges to be duplicated must be selected from the relevant ones (i.e. connected to vertices with odd degree) on that way, that the increase of the path length due to edge duplication must be the possible smallest. Therefore those pairing of the vertices with odd degree are selected, which have the shortest path connecting them.

The example unweighted graph in Figure [[#fig:exa_graph_cpp_unweighted|9]] shows a Non-Eulerian graph and the Chinese postman tour obtained by duplicating the edges [2,4] and [3,1].

<div id="fig:exa_graph_cpp_unweighted" class="figure">

[[Datei:exa_graph_cpp_unweighted.jpg|460px|thumb|center|Figure 9: Example Non-Eulerian unweighted graph with Chinese postman tour]]

</div>
Similarly the example Non-Eulerian weighted graph in Figure [[#fig:exa_graph_cpp_weighted|10]] illustrates the construction of the Chinese postman by duplicating the edges [2,4], [4,6] and [5,1]. Here duplicating [2,4] together with [4,6] instead of [2,6] inserts shorter path (i.e. accumulated weight 2+1= 3 instead of 5). Similarly duplicating [5,1] instead of [5,3] together with [3,1] inserts shorter path (i.e. accumulated weight 1 instead of 1+2=3).

<div id="fig:exa_graph_cpp_weighted" class="figure">

[[Datei:exa_graph_cpp_weighted.jpg|460px|thumb|center|Figure 10: Example Non-Eulerian weighted graph with Chinese postman tour]]

</div>
<span id="algorithm-for-chinese-postman-problem"></span>
=== Algorithm for Chinese postman problem ===

Based on the above considerations the algorithm for finding the Chinese postman route can be given schematically by means of its steps in Algorithm 3.

<br />
Algorithm 3 Algorithm for Chinese postman problem<br />
<span>'''—————————————————————————————'''</span><br />
Input: Undirected graph <math display="inline">\boldsymbol{G}</math>.<br />
Output: Chinese postman route.<br />
<span>'''—————————————————————————————'''</span><br />
1 if grap <math display="inline">\boldsymbol{G}</math> is Eulerian<br />
2    Find an Eulerian cycle in <math display="inline">\boldsymbol{G}</math><br />
3    <math display="inline">totalWeight</math> = sum of all edge weights of <math display="inline">\boldsymbol{G}</math><br />
4    return Eulerian cycle and <math display="inline">totalWeight</math><br />
5 else<br />
6    Determine <math display="inline">N</math> from graph, <math display="inline">N =|\mathcal{V}|</math><br />
7    Find all vertices with odd degree and store in array <math display="inline">oddVertices</math><br />
8    Construct the complete graph <math display="inline">\boldsymbol{C}</math> from odd vertices together with edges<br />
<math display="inline">\mathrm{\ \ \ \ \ }</math>representing shortest paths among any pairs of odd vertices<br />
9    Find minimum weight perfect matching in <math display="inline">\boldsymbol{C}</math>, i.e the set of edges<br />
<math display="inline">\mathrm{\ \ \ \ \ }</math> reaching every odd vertices and together having smallest sum of weights.<br />
<math display="inline">\mathrm{\ \ \ \ \ }</math> This set of edges is called minimum T-join.<br />
10   Extend the graph <math display="inline">\boldsymbol{G}</math> by adding all edges from minimum T-join<br />
<math display="inline">\mathrm{\ \ \ \ \ }</math> resulting in extended graph <math display="inline">\boldsymbol{H}</math><br />
12   Find an Eulerian cycle in <math display="inline">\boldsymbol{H}</math><br />
13   <math display="inline">totalWeight</math> = sum of all edge weights of <math display="inline">\boldsymbol{H}</math><br />
14   return Eulerian cycle of <math display="inline">\boldsymbol{H}</math> and <math display="inline">totalWeight</math><br />
15 end<br />
<span>'''—————————————————————————————'''</span><br />


The numerical complexity of the above minimum T-join based algorithm for solving the Chinese postman problem is <math display="inline">\mathcal{O}(|\mathcal{V}|^3)</math>, since both setting up the complete graph, and finding minimum weight perfect matching in it takes <math display="inline">\mathcal{O}(|\mathcal{V}|^3)</math> computational steps.

<span id="minimum-spanning-tree---kruskals-algorithm"></span>
== Minimum spanning tree - Kruskal’s algorithm ==

A spanning tree of a graph is a tree including every vertices of the graph. The number of edges of a spanning tree is <math display="inline">|\mathcal{V}|-1</math>, since the <math display="inline">|\mathcal{V}|</math>-th edge would introduce a cycle and it were not any more a tree.

The minimum spanning tree (MST) is defined for a weighted, undirected, connected graph <math display="inline">\boldsymbol{G}</math>, as a spanning tree with the minimal accumulated weights.

Kruskal’s algorithm can be used to determine the MST of graph <math display="inline">\boldsymbol{G}</math>. In the Kruskal’s algorithm all edges of <math display="inline">\boldsymbol{G}</math> are sorted according to their weights in increasing order. Then the algorithm iteratively adds the next edge from the sorted list, i.e. the edge with the smallest weight, together with their vertexes to MST, if the newly added edge does not induce a cycle. The algorithm proceeds until every edge on the list is checked. On this way the resulted graph will have <math display="inline">|\mathcal{V}|-1</math> edge, so it will be a spanning tree and the way of constructing implies that it will have the least accumulated weights.

The algorithm takes in each step the locally optimal decision due to adding the edge with the smallest weight among the still available ones. Therefore Kruskal’s algorithm is a greedy algorithm.

The algorithm is shown schematically in Algorithm 4.

<br />
Algorithm 4 Kruskal’s algorithm for detrmining MST<br />
<span>'''—————————————————————————————'''</span><br />
Input: Undirected weighted connected graph <math display="inline">\boldsymbol{G}</math>.<br />
Output: MST of <math display="inline">\boldsymbol{G}</math>.<br />
<span>'''—————————————————————————————'''</span><br />
1 Initialise graph MST to be set empty.<br />
2 Sort every edges of <math display="inline">\boldsymbol{G}</math> in increasing weight order and insert them,<br />
<math display="inline">\mathrm{\ \ }</math> together with their vertexes into array <math display="inline">sortedListEdges[]</math><br />
3 for <math display="inline">v=0,\ldots size(sortedListEdges)-1</math><br />
4    if inserting <math display="inline">sortedListEdges[v]</math> into MST does not induce a cycle<br />
5      Add <math display="inline">sortedListEdges[v]</math> into MST<br />
6    end<br />
7 end<br />
8 return MST<br />
<span>'''—————————————————————————————'''</span><br />


The computational complexity of the algorithm is <math display="inline">\mathcal{O}(|\mathcal{E}|*log(|\mathcal{E}|))</math>, since sorting the edges has <math display="inline">\mathcal{O}(|\mathcal{E}|*log(|\mathcal{E}|))</math> complexity, iterating through every edges and checking cycle has <math display="inline">\mathcal{O}(|\mathcal{E}|*log(|\mathcal{V}|))</math> and <math display="inline">\mathcal{O}(log(|\mathcal{V}|) =\mathcal{O}(log(|\mathcal{E}|)</math> due to <math display="inline">|\mathcal{E}|</math> is at most <math display="inline">|\mathcal{V}|^2</math>.

The memory need of the algorithm is <math display="inline">\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)</math>, which is needed to store edges together with their vertexes.

<span id="traveling-salesman-problem"></span>
== Traveling salesman problem ==

The Traveling Salesman Problem (TSP) originates from a context of cities and given distances among them. TSP is to look for the shortest path that goes through each city exactly once and returns to the starting city. Usually there exists a route between any pair of cities with some given distance. In graph theory context an equivalent formulation of TSP can be given as looking for a path with the least accumulated weights in a weighted, often complete graph, that goes through each vertex exactly once and returns to the starting vertex. This is equivalent with finding the Hamiltonian cycle with the minimum accumulated weight in a weighted, often complete graph. Thus the TSP is more general than Hamilton cycle problem and hence Hamilton cycle problem is a special case of TSP. The resulted path can be also called as TSP path.

The TSP was formulated mathematically in the 19th century and was first studied mathematically in the 1930s. The decision problem version of TSP is an NP-complete problem, so TSP is NP-hard. TSP is one of the most intensively investigated problem in combinatorial optimization, since it is used as benchmark for other optimization methods in terms of computational complexity.

Some properties of TSP can be provided as

* Symmetric and asymmetric TSP. In symmetric TSP the distance between two cities is the same in both direction, which leads to a formulation in graph theory context to a TSP on undirected graph. In asymmetric TSP either do not exist a path between two cities in both direction or the distances are different excluding the higher one from the TSP formulation. In these cases the formulation in graph theory context yileds a TSP on directed graph.
* Completing the graph by adding edges with sufficiently long distances will not affect the optimal path.
* The path to be a cycle or an open path does not make difference in the computational complexity of TSP (like in case of Hamilton path problem).

The TSP has applications in numerous fields, like logistics, route planning in transport networks, manufacturing of microchips and DNA sequencing. One-way streets, airfares with different departure and arrival fees are real-world scenarios for applying asymmetric TSP.

<span id="generalizations-of-tsp"></span>
=== Generalizations of TSP ===

Several generalizations of TSP are listed below.

* The travelling politician problem (also called as &quot;generalized travelling salesman problem&quot;) has a context with states having one or more cities and the travelling man must visit exactly one city from each state. It has been shown that travelling politician problem can be led back to standard TSP with modified distance matrix.
* The travelling purchaser problem has a purchaser, who has to buy a set of products, which can be bought in more cities but at different prices. The optimization objective is to find a path among a subset of cities that enables to buy all the products with minimal total cost (=taveling cost + purchasing cost).
* Vehicle routing problem.
* Ring star problem ([Labbé et al.(2004)]).

<span id="integer-linear-programming-formulation"></span>
=== Integer linear programming formulation ===

In order to form the TSP as Integer Linear Programming (ILP) optimization, several variables must be introduced. Let <math display="inline">N</math> denote the number of cities (vertices), i.e. <math display="inline">N = |\mathcal{V}|</math>. Let <math display="inline">c_{ij}</math> stand for the distances (weights) between the cities (vertices) <math display="inline">i</math> and <math display="inline">j</math>, for <math display="inline">i,j = 1, \ldots, N</math>. Let <math display="inline">x_{ij}</math> be a decision variable describing whether the path goes from city (vertix) <math display="inline">i</math> to <math display="inline">j</math>, or not for <math display="inline">i,j = 1, \ldots, N</math>. In other words <math display="block">x_{ij} = \left\{
\begin{aligned}
1, \mathrm{\ \ } \mathrm{~if~path~goes~i \rightarrow j}  \\
0, \mathrm{\ \ } \mathrm{~otherwise~~~~~~~~~~~}
\end{aligned}
\right\}.</math> The integer nature of the values <math display="inline">0</math> and <math display="inline">1</math> makes this optimization problem an ILP. The objective function of the optimization task is to minimize the path length (= accumulated weights), in other word

<math display="block">\arg \min_{x_{ij}}  \sum_{i=1}^{N} \sum_{j=1,~j \neq i}^{N} c_{ij} x_{ij} ~j = 1, \ldots, N.</math>

However without further constraints this optimization considers not only paths, which are characterized by also leaving each reached vertex, but all set of edges enabling the minimum being at <math display="inline">x_{ij}=0</math> for every <math display="inline">i,j \in \mathcal{V}</math>. Therefore further constraints are necessary to ensure that paths are considered and each vertex is visited exactly once. These requirements can be forced by formulating the following further two constraints, which force that the path reaches each vertex exactly once and leaves each vertex exactly once <math display="block">\begin{aligned}
\sum_{i=1,~i \neq j}^{N} x_{ij} = 1, ~~ j = 1, \ldots, N, \\
\sum_{j=1,~j \neq i}^{N} x_{ij} = 1, ~~ i = 1, \ldots, N. 
\end{aligned}</math>

These constraints ensure that the selected way looks locally as path and all vertices are visited, but still allow that the selected set of edges comprises several local paths each of them visiting only a disjunct subset of vertices instead of one global path visiting every vertices. This global path requirement makes TSP a difficult problem. There are more ways to formulate this global path requirement as a linear constraint. The Miller-Tucker-Zemlin formulation introduces dummy variables <math display="inline">u_i</math> for keeping track the order of visit the city <math display="inline">i</math>, for <math display="inline">i = 1, \ldots, N</math>. The path starts with visiting city <math display="inline">1</math>. The global path requirement is ensured by forcing <math display="inline">u_j</math> being higher than <math display="inline">u_i</math> when city <math display="inline">i</math> is visited before city <math display="inline">j</math>, for <math display="inline">i = 2, \ldots, N</math>. More precisely <math display="inline">u_j</math> must be higher than <math display="inline">u_i</math> at least by one when city <math display="inline">j</math> locates on the path after city <math display="inline">i</math>, and otherwise by a values less than <math display="inline">N</math> to ensure that <math display="inline">x_{ij}=0</math> does not force an unwanted relation between <math display="inline">u_i</math> and <math display="inline">u_j</math>. Since city <math display="inline">1</math> is left out from these constraint, it ensures that the optimal path must return to city <math display="inline">1</math>, otherwise the value of the dummy variable of the city visited after city <math display="inline">N-1</math> would be less that <math display="inline">u_{N-1}</math>, which would violate the constraint. The city <math display="inline">1</math> is the only one for which a decrease in value of the dummy variable allowed when the path reaches city <math display="inline">1</math>. These considerations lead to the formulation of the global path requirement as a linear constraint as <math display="block">u_i -u_j + 1 \leq (N-1)(1-x_{ij}) ~~ i,j \in \{2, \ldots, N \}  \mathrm{~and~} i \leq j.</math>

Putting all these together gives the Miller-Tucker-Zemlin ILP formulation of the TSP as <math display="block">\begin{aligned}
\arg \min_{x_{ij}}  \sum_{i=1}^{N} \sum_{j=1,~j \neq i}^{N} c_{ij} x_{ij},~\ldots, N, ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\
\mathrm{~subject~to} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\
\mathrm{~constraint~}1.~~~ \sum_{i=1,~i \neq j}^{N} x_{ij} = 1, ~~ j = 1, \ldots, N,  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\
\mathrm{~constraint~}2.~~~ \sum_{j=1,~j \neq i}^{N} x_{ij} = 1, ~~ i = 1, \ldots, N,  \mathrm{~and~} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\ 
\mathrm{~constraint~}3.~~~ u_i -u_j + 1 \leq (N-1)(1-x_{ij}) ~~ i,j \in \{2, \ldots, N \}  \mathrm{~and~} i \leq j.
\end{aligned}</math>

<span id="algorithms-for-tsp"></span>
=== Algorithms for TSP ===

<span>'''''<math display="inline">\mathrm{\ \ \ \ \ \ }</math> Exact algorithm - Brute-force search'''''</span>

The brute-force search tries all the possible permutations of all the <math display="inline">|V|</math> vertices and selects the one with the lowest accumulated weights. This results in <math display="inline">|V|!</math> different sequence of vertices the <math display="inline">|V|</math> vertices, so the computational complexity of this algorithm is <math display="inline">\mathcal{O}(|\mathcal{V}|!)</math>. Hence this approach becomes intractable already for number of cities in the magnitude of <math display="inline">20</math>.

<span>'''<math display="inline">\mathrm{\ \ \ \ }</math> Approximate algorithms'''</span>

Due to the NP-completeness of the TSP the exact solution becomes intractable very fast as the number of cities increases. Therefore there is a need for establishing approximate algorithms for the TSP.

<span>'''''<math display="inline">\mathrm{\ \ \ \ \ \ }</math> Nearest neighbour algorithm'''''</span>

The Nearest Neighbour (NN) algorithm selects the nearest not yet visited neighbour city at each step. Thus its decision is locally optimal in each step, therefore it is a greedy algorithm. Its schematic representation is shown in Algorithm 5.

<br />
Algorithm 5 Nearest neighbour approximate algorithm for TSP<br />
<span>'''—————————————————————————————'''</span><br />
Input: Undirected weighted graph.<br />
Output: Hamiltonian cycle with minimum accumulated weights.<br />
<span>'''—————————————————————————————'''</span><br />
1 Determine <math display="inline">N</math> from graph, <math display="inline">N =|\mathcal{V}|</math><br />
2 Initialize <math display="inline">path</math> array, set <math display="inline">path[0]=1</math> and set <math display="inline">totalWeight = 0</math><br />
<math display="inline">\mathrm{\ \ }</math> (<math display="inline">path</math> array =sequence of <math display="inline">N</math> vertices)<br />
3 for <math display="inline">v=1,\ldots N-1</math><br />
4   Select nearest not yet visited city among neighbours of city <math display="inline">path[v-1]</math>, <math display="inline">u</math><br />
5   <math display="inline">path[v]=u</math><br />
6   <math display="inline">totalWeight += weight(path[v-1], u)</math><br />
7 end<br />
8 return <math display="inline">path</math>, <math display="inline">totalWeight</math><br />
<span>'''—————————————————————————————'''</span><br />


The computational complexity of the NN algorithm is <math display="inline">\mathcal{O}(|\mathcal{V}|)</math>. For city arrangement distributed randomly on the plane, the NN algorithms gives a path which is only 25% longer than the shortest one. However for specific city arrangements the NN algorithm can produce also the worst route.

<span>'''''<math display="inline">\mathrm{\ \ \ \ \ \ }</math> Christofides algorithm'''''</span>

The heuristic approach of Christofides is based on using graph theoretical results to compose an approximate algorithm. It utilizes that a TSP path can not be longer than an Eulerian path over all cities of the graph. Therefore first a subgraph including all cities must be found, than it is extended to be an Eulerian graph, afterwards the Eulerian path is determined in the Eulerian graph and finally it is converted to a TSP path (i.e. to visit each city only once). If the minimum spanning tree of the original graph is selected as first graph and it is made to be an Eulerian graph by doubling every edge in it, then the total length of an Eulerian path can not be more than twice the one of the TSP path. Note that the length of the path changes also at converting the Eulerian path to a TSP path. During this step, shortcut is created for each city visited twice by inserting an edge from the city before this to a city after this. On this way one can approximate a solution for the TSP. The steps of the Christofides algorithm are shown schematically in Algorithm 6.

<br />
Algorithm 6 Christofides approximate algorithm for TSP<br />
<span>'''—————————————————————————————'''</span><br />
Input: Undirected weighted graph.<br />
Output: Approximate TSP path.<br />
<span>'''—————————————————————————————'''</span><br />
1 Find a minimum spanning tree <math display="inline">\boldsymbol{T}</math> of the graph.<br />
2 Duplicate every edges of <math display="inline">\boldsymbol{T}</math> to create an Eulerian graph <math display="inline">\boldsymbol{M}</math><br />
3 Find an Eulerian path in <math display="inline">\boldsymbol{M}</math><br />
4 Convert Eulerian path to approximate TSP path by using shortcuts<br />
5 return approximate TSP path<br />
<span>'''—————————————————————————————'''</span><br />


The Christofides algorithm was one of the first approximation algorithm, which shown that establishing an approximation algorithms can be practically usable approach for solving exactly intractable problems.

An improved version of the algorithm is the algorithm of Christofides and Serdyukov, in whic a better way of creating an Eulerian graph is applied. This is done by applying the so called minimum weight matching. The steps of the algorithm of Christofides and Serdyukov can be seen schematically in Algorithm 7.

<br />
Algorithm 7 Approximate algorithm of Christofides and Serdyukov for TSP<br />
<span>'''—————————————————————————————'''</span><br />
Input: Undirected weighted graph.<br />
Output: Approximate TSP path.<br />
<span>'''—————————————————————————————'''</span><br />
1 Find a minimum spanning tree <math display="inline">\boldsymbol{T}</math> of the graph.<br />
2 Apply minimum weight matching to odd-degree vertices of <math display="inline">\boldsymbol{T}</math> giving graph <math display="inline">\boldsymbol{W}</math><br />
3 Find optimal Eulerian path in <math display="inline">\boldsymbol{W}</math><br />
4 Convert Eulerian path to approximate TSP path by using shortcuts<br />
5 return approximate TSP path<br />
<span>'''—————————————————————————————'''</span><br />


Approximate algorithm of Christofides and Serdyukov gives an approximate TSP path with accumulated weights, which is at most 1,5 times higher than the one of the optimal TSP path. The computational complexity of the approximate algorithm of Christofides and Serdyukov is <math display="inline">\mathcal{O}(|\mathcal{V}|^3)</math>, which is mainly caused by minimum weight matching algorithm part.

<span id="shortest-path-problem"></span>
== Shortest path problem  ==

The shortest path in a weighted graph between two vertices is the path connecting them with the smallest accumulated weight. There are more algorithm for finding shortest path, each with a slightly different applicability scope.

Besides of Diskstra’s algoritm another common algorithms are the [https://en.wikipedia.org/wiki/Bellman-Ford_algorithm Bellman-Ford] and the [https://en.wikipedia.org/wiki/Floyd-Warshall_algorithm Floyd Warshall] algorithms.

<span id="dijkstra-algorithmus"></span>
=== Dijkstra-Algorithmus ===

Diskstra’s algorithm finds the shortest path from a given source vertex to every vertices in a weighted graph <math display="inline">\boldsymbol{G}</math>. The graph must not contain negative edge, since in that case the algorithm fails.

The idea of Diskstra’s algorithm is an iterative extension of shortest path tree (SPT) containing a subtree with vertices, for which the shortest paths from the a given source have already been found. The vertices outside of SPT have also minimum distance values assigned during the intermediate steps of the processing. The minimum distance values of vertices being neighbour of any vertices of SPT and locating outside of SPT represent the minimum distance from source vertex to the considered vertex via every possible routes over the vertices of the actual SPT. The iterative extension of SPT is performed by selecting the vertex <math display="inline">u</math> with the shortest minimum distance among the vertices locating outside of SPT, adding this vertex <math display="inline">u</math> together with its minimum distance to SPT and reevaluating the minimum distances of each vertex <math display="inline">v</math> locating outside of the updated SPT and being the neighbour of <math display="inline">u</math>. During the reevaluation the minimum distance of <math display="inline">v</math> is compared to the sum (minimum distance of <math display="inline">v</math> + weight of (<math display="inline">v</math>- <math display="inline">u</math>)) and if the later is smaller then the minimum distance of <math display="inline">v</math> will be updated.

The schematical representation of the algorithm can be seen in Algorithm 8.

<br />
Algorithm 8 Dijkstra-Algorithmus for determining SPT<br />
<span>'''—————————————————————————————'''</span><br />
Inputs:<br />
- Undirected weighted connected graph <math display="inline">\boldsymbol{G}</math>.<br />
- Source vertex <math display="inline">s</math>.<br />
Output: Array of minimum distances to every vertices <math display="inline">minDist[]</math>.<br />
<span>'''—————————————————————————————'''</span><br />
1 Create an adjacenty matrix <math display="inline">{\bf S}</math> for maintaining SPT with vertices (subtree),<br />
<math display="inline">\mathrm{\ \ \ }</math>for which the shortest paths from the a given source have already been found<br />
<math display="inline">\mathrm{\ \ \ }</math>and initialize it to empty.<br />
<math display="inline">\mathrm{\ \ \ }</math>Matrix <math display="inline">{\bf S}</math> stores already found minimum distance values for its vertices.<br />
2 Create and adjacency matrix <math display="inline">{\bf A}</math> for representing the graph <math display="inline">\boldsymbol{R}</math> being a<br />
<math display="inline">\mathrm{\ \ \ }</math>subgraph of <math display="inline">\boldsymbol{G}</math> containing vertices locating outside of SPT<br />
<math display="inline">\mathrm{\ \ \ }</math>and every edges of them. Matrix <math display="inline">{\bf A}</math> stores also actual values of<br />
<math display="inline">\mathrm{\ \ \ }</math>minimum distance to every vertices of <math display="inline">\boldsymbol{R}</math>.<br />
<math display="inline">\mathrm{\ \ \ }</math>Initialize all these distance values to <math display="inline">\infty</math>, and for the source vertex<br />
<math display="inline">\mathrm{\ \ \ }</math>set the minimum distance to the value <math display="inline">0</math>.<br />
3 while matrix <math display="inline">{\bf A}</math> is not empty (=not all vertices are moved from it)<br />
4    take a vertex <math display="inline">u</math> from subgraph matrix <math display="inline">{\bf A}</math> with the smallest minimum distance<br />
5    add vertex <math display="inline">u</math> with its minimum distance and its edge connecting it to SPT<br />
6     matrix <math display="inline">{\bf S}</math><br />
7      for each vertex <math display="inline">v</math> of graph <math display="inline">\boldsymbol{R}</math> being neighbour of <math display="inline">u</math><br />
8        (update minimum distance of vertex <math display="inline">v</math> in matrix <math display="inline">{\bf A}</math>: )<br />
9        if minimum distance of <math display="inline">u</math> + weight of (<math display="inline">v</math>- <math display="inline">u</math>) &lt; minimum distance of <math display="inline">v</math><br />
10         minimum distance of <math display="inline">v</math> = minimum distance of <math display="inline">u</math> + weight of (<math display="inline">v</math>- <math display="inline">u</math>)<br />
11         mark edge of <math display="inline">v</math> to <math display="inline">u</math> as edge connecting to SPT<br />
12       end<br />
13     end<br />
14     remove the row of vertex <math display="inline">u</math> from subgraph matrix <math display="inline">{\bf A}</math><br />
15      (that means also removing vertex <math display="inline">u</math> from subgraph <math display="inline">\boldsymbol{R}</math>)<br />
16 end<br />
17 Build up array <math display="inline">minDist[]</math> from SPT matrix <math display="inline">{\bf S}</math><br />
18 return array <math display="inline">minDist[]</math><br />
<span>'''—————————————————————————————'''</span><br />


The computational complexity of the algorithm is <math display="inline">\mathcal{O}(|\mathcal{E}|*log(|\mathcal{V}|))</math>, since finding the vertex in the subgraph <math display="inline">\boldsymbol{R}</math> takes <math display="inline">\mathcal{O}(log(|\mathcal{V}|))</math> operations, which must be done for every vertices. Note that it is the same as <math display="inline">\mathcal{O}(|\mathcal{E}|*log(|\mathcal{E}|))</math> due to <math display="inline">\mathcal{O}(log(|\mathcal{V}|))= \mathcal{O}(log(|\mathcal{E}|))</math>.

The finding the vertex of subgraph <math display="inline">\boldsymbol{R}</math> with the smallest minimum distance can be implemented by the help of priority queue (or Heap). The standard usage of priority queue would overwrite minimum distance in the inserted pair (minimum distance - vertex) for the same vertex always by the minimum distance of the lastly checked edge to that vertex, which is not necessarily the smallest one among every edges. This can be resolved by inserting more copies of the pair (minimum distance - vertex) for the same vertex, since priority queue will take only the one of them with the smallest value of minimum distance.

Dijkstra’s algorithm assumes that in each intermediate step, the minimum distances of the vertices in SPT, are already the final ones, i.e. the shortest paths from the a given source to the vertices of SPT have already been found. This holds with non- negative weight, since in this case a new path to a vertex in SPT via any vertices of outside of SPT would increase the distance by a sum of non-negative weights which then can not be smaller then the distance marked in SPT as the minimum one. However this is not true in case of existence of negative weight, and thus for graphs with negative weights Dijkstra’s algorithm can return higher distance than than the real minimal one, i.e. wrong result. This is illustrated on the graph in Figure [[#fig:exa_graph_neg_weight|11]].

<div id="fig:exa_graph_neg_weight" class="figure">

[[Datei:exa_graph_neg_weight.jpg|460px|thumb|center|Figure 11: Example graph with negative weight]]

</div>
For this graph Dijkstra’s algorithm would give minimum distance for node <math display="inline">2</math> and <math display="inline">4</math> the value <math display="inline">4</math> and <math display="inline">6</math>, which is wrong, since the right value is <math display="inline">3</math> and <math display="inline">5</math>, respectively