Dijkstra's algorithm
Dijkstra's algorithm is an algorithm for solving Single Source Shortest Path problem which is to find shortest paths from a source vertex v to all other vertices in the graph.
Python(2.7.11) example
Implementation:
from heapq import heappop, heappush
inf = float('inf')
def dijkstra(G, s): # G is graph and G[u][v] is distance between u and v, and s is the source vertex
D, Q, S = {s:0}, [(0,s)], set() # After algorithm terminated, D[u] is the shortest distance between s and u
while Q:
dummy, u = heappop(Q)
if u in S:
continue
S.add(u)
for v in G.get(u, {}):
d = D.get(u, inf) + G[u][v]
if d < D.get(v, inf):
D[v] = d
heappush(Q, (D[v], v))
return D
Test:
G = {
'a': {'b': 1, 'c': 5},
'b': {'c': 2, 'd': 2},
'c': {'a': 2, 'b': 3},
'd': {'a': 1, 'c': 3}
}
print dijkstra(G, 'a')
Output:
{'a': 0, 'c': 3, 'b': 1, 'd': 3}
That means the distance from a to a is 0 and from a to b is 1 and so on.
Floyd–Warshall algorithm
Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge between all vertex pairs.
Python(2.7.11) example
Implementation:
from copy import deepcopy
inf = float('inf')
def floyd_warshall(G): # G is graph and G[u][v] is distance between u and v, and s is the source vertex
D = deepcopy(G) # After algorithm terminated, D[u][v] is the shortest distance between u and v
for v in D:
D[v][v] = 0
for k in D:
for u in D:
for v in D:
D[u][v] = min(D[u].get(v, inf), D[u].get(k, inf) + D[k].get(v, inf))
return D
Test:
G = {
'a': {'b': 1, 'c': 5},
'b': {'c': 2, 'd': 2},
'c': {'a': 2, 'b': 3},
'd': {'a': 1, 'c': 3},
}
print floyd_warshall(G)
Output:
{'a': {'a': 0, 'c': 3, 'b': 1, 'd': 3}, 'c': {'a': 2, 'c': 0, 'b': 3, 'd': 5}, 'b': {'a': 3, 'c': 2, 'b': 0, 'd': 2}, 'd': {'a': 1, 'c': 3, 'b': 2, 'd': 0}}
That means the distance from a to c is 3 and from c to a is 2 and so on.
Topological Sort
A topological ordering, or a topological sort, orders the vertices in a directed acyclic graph on a line, i.e. in a list, such that all directed edges go from left to right. Such an ordering cannot exist if the graph contains a directed cycle because there is no way that you can keep going right on a line and still return back to where you started from.
Formally, in a graph G = (V, E)
, then a linear ordering of all its
vertices is such that if G
contains an edge (u, v) ∈ E
from vertex u
to vertex v
then u
precedes v
in the ordering.
It is important to note that each DAG has at least one topological sort.
There are known algorithms for constructing a topological ordering of any DAG in linear time, one example is:
- Call
depth_first_search(G)
to compute finishing timesv.f
for each vertexv
- As each vertex is finished, insert it into the front of a linked list
- the linked list of vertices, as it is now sorted.
A topological sort can be performed in ϴ(V + E)
time, since the
depth-first search algorithm takes ϴ(V + E)
time and it takes Ω(1)
(constant time) to insert each of |V|
vertices into the front of
a linked list.
Many applications use directed acyclic graphs to indicate precedences among events. We use topological sorting so that we get an ordering to process each vertex before any of its successors.
Vertices in a graph may represent tasks to be performed and the edges
may represent constraints that one task must be performed before
another; a topological ordering is a valid sequence to perform the
tasks set of tasks described in V
.
Problem instance and its solution
Let a vertice v
describe a Task(hours_to_complete: int)
, i. e. Task(4)
describes a Task
that takes 4
hours to complete, and an edge e
describe a Cooldown(hours: int)
such that Cooldown(3)
describes a duration of time to cool down after a completed task.
Let our graph be called dag
(since it is a directed acyclic graph), and let it contain 5 vertices:
A <- dag.add_vertex(Task(4));
B <- dag.add_vertex(Task(5));
C <- dag.add_vertex(Task(3));
D <- dag.add_vertex(Task(2));
E <- dag.add_vertex(Task(7));
where we connect the vertices with directed edges such that the graph is acyclic,
// A ---> C ----+
// | | |
// v v v
// B ---> D --> E
dag.add_edge(A, B, Cooldown(2));
dag.add_edge(A, C, Cooldown(2));
dag.add_edge(B, D, Cooldown(1));
dag.add_edge(C, D, Cooldown(1));
dag.add_edge(C, E, Cooldown(1));
dag.add_edge(D, E, Cooldown(3));
then there are three possible topological orderings between A
and E
,
A -> B -> D -> E
A -> C -> D -> E
A -> C -> E
Sign up or log in
Save edit as a guest
Join Stack Overflow
We recognize you from another Stack Exchange Network site!
Join and Save Draft