首页 > itarticle > dijkstra algorithm

dijkstra algorithm

admin 11月 11, 2020 0

Induction:

Dijkstra’s algorithm is an algorithm for finding the shortest paths between
nodes in a graph, which may represent, for example, road networks. It was conce
ived by computer scientist Edsger W. Dijkstra in 1956 and published three years
later.

Dijkstra’s algorithm

Dijkstra’s algorithm finds a shortest path tree from a single source node, by
building a set of nodes that have minimum distance from the source.

The graph has the following:

  • vertices, or nodes, denoted in the algorithm by v or u;

  • weighted edges that connect two nodes: (u, v) denotean edge, and w(u,v)
    denotes its weight.

This is done by initializing three values:

  • dist, an array of distances from the source node s to each node in
    the graph, initialized the following way: dist(s) = 0; and for all oth
    er nodes v, dist(v) = ∞infty∞. This is done at the beginning because
    as the algorithm proceeds, the dist from the source to each node v in
    the graph will be recalculated and finalized when the shortest distance to
    v is found.

  • Q, a queue of all nodes in the graph. At the end of the algorithm’s
    progress, Q will be empty.

  • S, an empty set, to indicate which nodes the algorithm has visited.
    At the end of the algorithm’s run, S will contain all the nodes of
    the graph.

The algorithm proceeds as follows:

  1. While Q is not empty, pop the node v, that is not already in S,
    from Q with the smallest dist(v). In the first run, source node s
    will be chosen because dist(s) was initialized to 0. In the next run,
    the next node with the smallest dist value is chosen.

  2. Add node v to S, to indicate that v has been visited.

  3. Update dist values of adjacent nodes of the current node v as follows:
    for each new adjacent node u,

    • if dist(v) + weight(u,v) < dist(u), there is a new minimal distance
      found for u, so update dist(u) to the new minimal distance value;

    • otherwise, no updates are made to dist(u).

The algorithm has visited all nodes in the graph and found the smallest distance
to each node. distdistdist now contains the shortest path tree from source s.

==Note: The weight of an edge(u, v) is taken from the value associated with (u, v)
on the graph.==

Implmentation:

This is pseudocode for Dijkstra’s algorithm, mirroring Python syntax. It can be used in order to implement the algorithm in any language.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
function Dijkstra(Graph, source):
       dist[source]  := 0                     // Distance from source to source is set to 0
       for each vertex v in Graph:            // Initializations
           if v ≠ source
               dist[v]  := infinity           // Unknown distance function from source to each node set to infinity
           add v to Q                         // All nodes initially in Q

      while Q is not empty:                  // The main loop
          v := vertex in Q with min dist[v]  // In the first run-through, this vertex is the source node
          remove v from Q 

          for each neighbor u of v:           // where neighbor u has not yet been removed from Q.
              alt := dist[v] + length(v, u)
              if alt < dist[u]:               // A shorter path to u has been found
                  dist[u]  := alt            // Update distance of u

      return dist[]
  end function

This is the python code for the dijkstra algorithm.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
import heapq

class ():
    """ Nodes in the graph. """

    def __init__(self, number=0, weight=0):
        self.number = number
        self.weight = weight

    def __lt__(self, other):
        return self.weight < other.weight


def dijkstra_heap(graph, start):
    """ Dijkstra algorithm for heap optimization. """
    INF = 999999999
    dist = [INF for node in graph]
    path = [-1 for node in graph]
    visited = [False for node in graph]

    dist[start] = 0
    path[start] = start

    pq = list()
    heapq.heappush(pq, Node(start, 0))

    while pq:
        temp = heapq.heappop(pq)
        here = temp.number
        cost = temp.weight

        if visited[here]:
            continue
        else:
            visited[here] = True

        for node in graph[here]:
            if (not visited[node]) and (cost + graph[here][node] < dist[node]):
                dist[node] = cost + graph[here][node]
                path[node] = here
                heapq.heappush(pq, Node(node, dist[node]))

    display_path(graph, start, dist, path, visited)


def display_path(graph, start, dist, path, visted):
    """ Print the shortest path. """
    print("Path from " + str(start) + " node to other node :")

    routes = list()
    for i in range(len(graph)):
        route = list()
        if visted[i] and i != start:
            route.append(i)
            temp = path[i]
            while temp != start:
                route.append(temp)
                temp = path[temp]
            route.append(start)

        routes.append(route)

    for route in routes:
        if route:
            temp = str()
            for node in reversed(route):
                temp += "#" + str(node)
                if route.index(node) != 0:
                    temp += " -> "

            print("#" + str(start) + " -> " + str(route[0]) +
                  " : " + "weight:" + str(dist[route[0]]) + "t" + temp)

        elif routes.index(route) != start:
            print("#" + str(start) + " -> " + str(route[0]) +
                  " : " + "No Path!")
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能