Example 1: dijkstra algorithm c++
using namespace std;
int main()
{
int n = 9;
int mat[9][9] = { { 100,4,100,100,100,100,100,8,100},
{ 4,100,8,100,100,100,100,11,100},
{100,8,100,7,100,4,100,100,2},
{100,100,7,100,9,14,100,100,100},
{100,100,100,9,100,100,100,100,100},
{100,100,4,14,10,100,2,100,100},
{100,100,100,100,100,2,100,1,6},
{8,11,100,100,100,100,1,100,7},
{100,100,2,100,100,100,6,7,100}};
int src = 0;
int count = 1;
int path[n];
for(int i=0;i<n;i++)
path[i] = mat[src][i];
int visited[n] = {0};
visited[src] = 1;
while(count<n)
{
int minNode;
int minVal = 100;
for(int i=0;i<n;i++)
if(visited[i] == 0 && path[i]<minVal)
{
minVal = path[i];
minNode = i;
}
visited[minNode] = 1;
for(int i=0;i<n;i++)
if(visited[i] == 0)
path[i] = min(path[i],minVal+mat[minNode][i]);
count++;
}
path[src] = 0;
for(int i=0;i<n;i++)
cout<<src<<" -> "<<path[i]<<endl;
return(0);
}
Example 2: dijkstra's algorithm python
import sys
class Vertex:
def __init__(self, node):
self.id = node
self.adjacent = {}
self.distance = sys.maxsize
self.visited = False
self.previous = None
def __lt__(self, other):
return self.distance < other.distance
def add_neighbor(self, neighbor, weight=0):
self.adjacent[neighbor] = weight
def get_connections(self):
return self.adjacent.keys()
def get_id(self):
return self.id
def get_weight(self, neighbor):
return self.adjacent[neighbor]
def set_distance(self, dist):
self.distance = dist
def get_distance(self):
return self.distance
def set_previous(self, prev):
self.previous = prev
def set_visited(self):
self.visited = True
def __str__(self):
return str(self.id) + ' adjacent: ' + str([x.id for x in self.adjacent])
class Graph:
def __init__(self):
self.vert_dict = {}
self.num_vertices = 0
def __iter__(self):
return iter(self.vert_dict.values())
def add_vertex(self, node):
self.num_vertices = self.num_vertices + 1
new_vertex = Vertex(node)
self.vert_dict[node] = new_vertex
return new_vertex
def get_vertex(self, n):
if n in self.vert_dict:
return self.vert_dict[n]
else:
return None
def add_edge(self, frm, to, cost=0):
if frm not in self.vert_dict:
self.add_vertex(frm)
if to not in self.vert_dict:
self.add_vertex(to)
self.vert_dict[frm].add_neighbor(self.vert_dict[to], cost)
self.vert_dict[to].add_neighbor(self.vert_dict[frm], cost)
def get_vertices(self):
return self.vert_dict.keys()
def set_previous(self, current):
self.previous = current
def get_previous(self, current):
return self.previous
def shortest(v, path):
''' make shortest path from v.previous'''
if v.previous:
path.append(v.previous.get_id())
shortest(v.previous, path)
return
import heapq
def dijkstra(aGraph, start, target):
print('''Dijkstra's shortest path''')
start.set_distance(0)
unvisited_queue = [(v.get_distance(), v) for v in aGraph]
heapq.heapify(unvisited_queue)
while len(unvisited_queue):
uv = heapq.heappop(unvisited_queue)
current = uv[1]
current.set_visited()
for next in current.adjacent:
if next.visited:
continue
new_dist = current.get_distance() + current.get_weight(next)
if new_dist < next.get_distance():
next.set_distance(new_dist)
next.set_previous(current)
print('updated : current = %s next = %s new_dist = %s' \
% (current.get_id(), next.get_id(), next.get_distance()))
else:
print('not updated : current = %s next = %s new_dist = %s' \
% (current.get_id(), next.get_id(), next.get_distance()))
while len(unvisited_queue):
heapq.heappop(unvisited_queue)
unvisited_queue = [(v.get_distance(), v) for v in aGraph if not v.visited]
heapq.heapify(unvisited_queue)
if __name__ == '__main__':
g = Graph()
g.add_vertex('a')
g.add_vertex('b')
g.add_vertex('c')
g.add_vertex('d')
g.add_vertex('e')
g.add_vertex('f')
g.add_edge('a', 'b', 7)
g.add_edge('a', 'c', 9)
g.add_edge('a', 'f', 14)
g.add_edge('b', 'c', 10)
g.add_edge('b', 'd', 15)
g.add_edge('c', 'd', 11)
g.add_edge('c', 'f', 2)
g.add_edge('d', 'e', 6)
g.add_edge('e', 'f', 9)
print('Graph data:')
for v in g:
for w in v.get_connections():
vid = v.get_id()
wid = w.get_id()
print('( %s , %s, %3d)' % (vid, wid, v.get_weight(w)))
dijkstra(g, g.get_vertex('a'), g.get_vertex('e'))
target = g.get_vertex('e')
path = [target.get_id()]
shortest(target, path)
print('The shortest path : %s' % (path[::-1]))
Example 3: dijkstra's algorithm python
import sys
class Vertex:
def __init__(self, node):
self.id = node
self.adjacent = {}
self.distance = sys.maxint
self.visited = False
self.previous = None
def add_neighbor(self, neighbor, weight=0):
self.adjacent[neighbor] = weight
def get_connections(self):
return self.adjacent.keys()
def get_id(self):
return self.id
def get_weight(self, neighbor):
return self.adjacent[neighbor]
def set_distance(self, dist):
self.distance = dist
def get_distance(self):
return self.distance
def set_previous(self, prev):
self.previous = prev
def set_visited(self):
self.visited = True
def __str__(self):
return str(self.id) + ' adjacent: ' + str([x.id for x in self.adjacent])
class Graph:
def __init__(self):
self.vert_dict = {}
self.num_vertices = 0
def __iter__(self):
return iter(self.vert_dict.values())
def add_vertex(self, node):
self.num_vertices = self.num_vertices + 1
new_vertex = Vertex(node)
self.vert_dict[node] = new_vertex
return new_vertex
def get_vertex(self, n):
if n in self.vert_dict:
return self.vert_dict[n]
else:
return None
def add_edge(self, frm, to, cost = 0):
if frm not in self.vert_dict:
self.add_vertex(frm)
if to not in self.vert_dict:
self.add_vertex(to)
self.vert_dict[frm].add_neighbor(self.vert_dict[to], cost)
self.vert_dict[to].add_neighbor(self.vert_dict[frm], cost)
def get_vertices(self):
return self.vert_dict.keys()
def set_previous(self, current):
self.previous = current
def get_previous(self, current):
return self.previous
def shortest(v, path):
''' make shortest path from v.previous'''
if v.previous:
path.append(v.previous.get_id())
shortest(v.previous, path)
return
import heapq
def dijkstra(aGraph, start, target):
print '''Dijkstra's shortest path'''
start.set_distance(0)
unvisited_queue = [(v.get_distance(),v) for v in aGraph]
heapq.heapify(unvisited_queue)
while len(unvisited_queue):
uv = heapq.heappop(unvisited_queue)
current = uv[1]
current.set_visited()
for next in current.adjacent:
if next.visited:
continue
new_dist = current.get_distance() + current.get_weight(next)
if new_dist < next.get_distance():
next.set_distance(new_dist)
next.set_previous(current)
print 'updated : current = %s next = %s new_dist = %s' \
%(current.get_id(), next.get_id(), next.get_distance())
else:
print 'not updated : current = %s next = %s new_dist = %s' \
%(current.get_id(), next.get_id(), next.get_distance())
while len(unvisited_queue):
heapq.heappop(unvisited_queue)
unvisited_queue = [(v.get_distance(),v) for v in aGraph if not v.visited]
heapq.heapify(unvisited_queue)
if __name__ == '__main__':
g = Graph()
g.add_vertex('a')
g.add_vertex('b')
g.add_vertex('c')
g.add_vertex('d')
g.add_vertex('e')
g.add_vertex('f')
g.add_edge('a', 'b', 7)
g.add_edge('a', 'c', 9)
g.add_edge('a', 'f', 14)
g.add_edge('b', 'c', 10)
g.add_edge('b', 'd', 15)
g.add_edge('c', 'd', 11)
g.add_edge('c', 'f', 2)
g.add_edge('d', 'e', 6)
g.add_edge('e', 'f', 9)
print 'Graph data:'
for v in g:
for w in v.get_connections():
vid = v.get_id()
wid = w.get_id()
print '( %s , %s, %3d)' % ( vid, wid, v.get_weight(w))
dijkstra(g, g.get_vertex('a'), g.get_vertex('e'))
target = g.get_vertex('e')
path = [target.get_id()]
shortest(target, path)
print 'The shortest path : %s' %(path[::-1])
Example 4: dijkstra algorithm
//djikstra's algorithm using a weighted graph (STL)
//code by Soumyadepp
//insta: @soumyadepp
//linkedinID: https://www.linkedin.com/in/soumyadeep-ghosh-90a1951b6/
using namespace std;
//to find the closest unvisited vertex from the source
//note that numbering of vertices starts from 1 here. Calculate accordingly
ll minDist(ll dist[], ll n, bool visited[])
{
ll min = INT_MAX;
ll minIndex = 0;
for (ll i = 1; i <= n; i++)
{
if (!visited[i] && dist[i] <= min)
{
min = dist[i];
minIndex = i;
}
}
return minIndex;
}
//djikstra's algorithm for single source shortest path
void djikstra(vector<pair<ll, ll>> *g, ll n, ll src)
{
bool visited[n + 1];
ll dist[n + 1];
for (ll i = 0; i <= n; i++)
{
dist[i] = INT_MAX;
visited[i] = false;
}
dist[src] = 0;
for (ll i = 0; i < n - 1; i++)
{
ll u = minDist(dist, n, visited);
visited[u] = true;
for (ll v = 0; v < g[u].size(); v++)
{
if (dist[u] + g[u][v].second < dist[g[u][v].first])
{
dist[g[u][v].first] = dist[u] + g[u][v].second;
}
}
}
cout << "VERTEX : DISTANCE" << endl;
for (ll i = 1; i <= n; i++)
{
if (dist[i] != INT_MAX)
cout << i << " " << dist[i] << endl;
else
cout << i << " "
<< "not reachable" << endl;
}
cout << endl;
}
int main()
{
//to store the adjacency list which also contains the weight
vector<pair<ll, ll>> *graph;
ll n, e, x, y, w, src;
cout << "Enter number of vertices and edges in the graph" << endl;
cin >> n >> e;
graph = new vector<pair<ll, ll>>[n + 1];
cout << "Enter edges and weight" << endl;
for (ll i = 0; i < e; i++)
{
cin >> x >> y >> w;
//checking for invalid edges and negative weights.
if (x <= 0 || y <= 0 || w <= 0)
{
cout << "Invalid parameters. Exiting" << endl;
exit(-1);
}
graph[x].push_back(make_pair(y, w));
graph[y].push_back(make_pair(x, w));
}
cout << "Enter source from which you want to find shortest paths" << endl;
cin >> src;
if (src >= 1 && src <= n)
djikstra(graph, n, src);
else
cout << "Please enter a valid vertex as the source" << endl;
return 0;
}
//time complexity : O(ElogV)
//space complexity: O(V)
Example 5: Dijkstra's Weighted Graph Shortest Path in c++
int minDistance(int dist[], bool sptSet[])
{
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
void printSolution(int dist[])
{
printf("Vertex \t\t Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t\t %d\n", i, dist[i]);
}
void dijkstra(int graph[V][V], int src)
{
int dist[V];
bool sptSet[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printSolution(dist);
}
int main()
{
int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
dijkstra(graph, 0);
return 0;
}
Example 6: dijkstra's algorithm
n = int(input("Enter the number of vertices of the graph"))
vertices = [[0, 0, 1, 1, 0, 0, 0],
[0, 0, 1, 0, 0, 1, 0],
[1, 1, 0, 1, 1, 0, 0],
[1, 0, 1, 0, 0, 0, 1],
[0, 0, 1, 0, 0, 1, 0],
[0, 1, 0, 0, 1, 0, 1],
[0, 0, 0, 1, 0, 1, 0]]
edges = [[0, 0, 1, 2, 0, 0, 0],
[0, 0, 2, 0, 0, 3, 0],
[1, 2, 0, 1, 3, 0, 0],
[2, 0, 1, 0, 0, 0, 1],
[0, 0, 3, 0, 0, 2, 0],
[0, 3, 0, 0, 2, 0, 1],
[0, 0, 0, 1, 0, 1, 0]]
def to_be_visited():
global visited_and_distance
v = -10
for index in range(num_of_vertices):
if visited_and_distance[index][0] == 0 \
and (v < 0 or visited_and_distance[index][1] <=
visited_and_distance[v][1]):
v = index
return v
num_of_vertices = len(vertices[0])
visited_and_distance = [[0, 0]]
for i in range(num_of_vertices-1):
visited_and_distance.append([0, sys.maxsize])
for vertex in range(num_of_vertices):
to_visit = to_be_visited()
for neighbor_index in range(num_of_vertices):
if vertices[to_visit][neighbor_index] == 1 and
visited_and_distance[neighbor_index][0] == 0:
new_distance = visited_and_distance[to_visit][1]
+ edges[to_visit][neighbor_index]
if visited_and_distance[neighbor_index][1] > new_distance:
visited_and_distance[neighbor_index][1] = new_distance
visited_and_distance[to_visit][0] = 1
i = 0
for distance in visited_and_distance:
print("Distance of ", chr(ord('a') + i),
" from source vertex: ", distance[1])
i = i + 1