# Example: Dijkstra's shortest path algorithm with EOL/EVL

```// This script implements Dijkstra"s shortest
// path algorighm

var s : Node;
s = Node.allInstances.select(n|n.label = "a").first();

for (n in Node.allInstances) {
n.~distance = 10000;
}

s.~distance = 0;

var Q : Sequence(Node);
Q = Node.allInstances.clone();

while (not Q.isEmpty()) {
var u : Node;
u = Q.extractMin();
for (e in u.outgoing) {
var v : Node;
v = e.target;
if (u.~distance + e.weight < v.~distance) {
v.~distance = u.~distance + e.weight;
v.~previous = u;
}
}
}

// Print distances and paths
for (n in Node.allInstances){
("Distance of " + n.label + " from " + s.label + " : " +
n.~distance + " via " + n.getPath()).println();
}

operation Sequence(Node) extractMin() : Node {
var min : Node;
min = self.select(n|self.forAll(
n1|n.~distance <= n1.~distance)).first();
self.remove(min);
return min;
}

operation Node getPath() : String {
if (self.~previous.isDefined()) {
return self.~previous.getPath() + "->" + self.label;
}return self.label;
}```
```context Node {

constraint NotInCycle {
check : not self.allIncoming().includes(self)
message : "Node " + self.label +
" is part of a directed cycle"
}

}

context Edge {

constraint MustDefineSource {

check : self.source.isDefined()

message : "Edge does not have a source node"

}

constraint MustDefineTarget {
check : self.target.isDefined()

message : "Edge does not have a target node"
}

constraint PositiveWeight {

guard : self.satisfies("MustDefineSource") and
self.satisfies("MustDefineTarget")

check : self.weight >= 0

message : "Edge " + self.source.label + "->" +
self.target.label + " has a negative weight"

}

}

operation Node allIncoming() : Set {
return self.allIncoming(Set{});
}

operation Node allIncoming(visited : Set) : Set {
for (n in self.incoming.collect(e|e.source)) {
if (not visited.includes(n)) {
}
}
return visited;
}```
```@namespace(uri="DirectedGraph", prefix="DirectedGraph")
package DirectedGraph;

class Graph {
val GraphElement[*]#graph contents;
}

abstract class GraphElement {
ref Graph#contents graph;
}

class Node extends GraphElement {
attr String label;
ref Edge[*]#source outgoing;
ref Edge[*]#target incoming;
}

class Edge extends GraphElement {
attr Integer weight;
ref Node#outgoing source;
ref Node#incoming target;
}```

Clone Epsilon's Git repository and then:

Once you have checked out/imported the code, to run the example you need to go through the following steps:

1. register any .ecore metamodels in the org.eclipse.epsilon.examples.shortestpath project
2. right click the .launch file in the org.eclipse.epsilon.examples.shortestpath project
3. select Run as... and click the first item in the menu that pops up

#### What's this?

In this example, we use EOL and EVL to implement Dijkstra's shortest path algorithm.

#### What are .emf files?

.emf files are Ecore metamodels expressed using the Emfatic textual syntax.

#### Even more examples...

More examples are available in the examples folder of the Git repository.