# Demo entry 6331297

Pojo

Submitted by anonymous on Dec 01, 2016 at 19:44
Language: Python 3. Code size: 5.1 kB.

```    """On this task I created a graph data structure, which contains two classe: vertex and graph
Each class has its own attributes and funtions.
After the creation of the data structure, I implemented the Dijkstra algorithm.
Dijkstra finds the least expensive path, from start to end.

//GRAPH\\

2
---(B)-------------(C)---
2 ____/    | \     4       |    \____ 1
____/       2 |  -----------  | 3       \____
/              |       4     \ |      6       \
(A)             (D)-------------(E)-------------(H)
\____          |       3     / |
\____   3 |  -----------  | 7
1     \    | /     5       |
---(F)-------------(G)

"""
class Vertex:

def __init__(self, vertex):
self.vertex = vertex
self.neighbours = {}
self.distance = 0
self.previous = None

#adds the value to the neighbours dictionary, KEY:VALUE -> Vertex:Weight
self.neighbours[vertex] = weight

#gets the COST between two vertices
def get_weight(self, vertex):
return self.neighbours[vertex]

#finds all the neighbours of that vertex
def get_neighbours(self):
return self.neighbours.keys()

#sets the distance (also called tentative weight)
def set_distance(self, distance):
self.distance = distance

def get_distance(self):
return self.distance

class Graph:

def __init__(self):
self.dictionary = {}

newVertex = Vertex(vertex)
self.dictionary[vertex] = Vertex(vertex)
return newVertex

#gets all vertices in the graph
def get_vertices(self):
return self.dictionary.keys()

def Dijkstra(g, start, end):
current = start
for n in g.get_vertices():
#sets all the TW to infinite
g.dictionary[n].set_distance(float("inf"))
#start tw is 0
g.dictionary[start].set_distance(0)
visited = []
path = []
while current != end:
#get all the neighbours to the current node
for node in g.dictionary[current].get_neighbours():
if g.dictionary[current].get_distance() + g.dictionary[current].get_weight(node) < node.distance :
node.set_distance(g.dictionary[current].get_distance() + g.dictionary[current].neighbours[node])
#mentains the path, so it can be backtracked into a result
node.previous = current
visited.append(current)
minn = float("inf")
for n in g.dictionary[current].get_neighbours():
if n.vertex not in visited and n.distance < minn:
current = n.vertex
minn = n.distance
#creates the path, from the start to end
condition = True
while condition:
if end != start:
path.append(end)
end = g.dictionary[end].previous
else:
path.append(end)
condition = False

print (path[::-1], "of cost :",  g.dictionary[path[0]].distance)

if __name__ == "__main__":

g = Graph()