dijkstra 27s algorithm python

Solutions on MaxInterview for dijkstra 27s algorithm python by the best coders in the world

showing results for - "dijkstra 27s algorithm python"
Mariangel
14 Jul 2018
1//Dijkstra's Algorithm (Using priority queue)
2//Watch Striver graph series on youtube I learned from there
3#include<bits/stdc++.h>
4using namespace std;
5void addedge(vector<pair<int,int>>adj[],int u,int v,int w)
6{
7    adj[u].push_back(make_pair(v,w));
8    adj[v].push_back(make_pair(u,w));
9}
10void Dijkstra(vector<pair<int,int>>adj[],int source,int n)
11{
12    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> prior; //Min-Heap storing will store distance and node
13    vector<int>dist(n,INT_MAX);
14    dist[source]=0;
15    prior.push(make_pair(0,source));
16    while(!prior.empty())
17    {
18        int distance=prior.top().first;
19        int node=prior.top().second;
20        prior.pop();
21        for(auto it:adj[node])
22        {
23            int next_node=it.first;
24            int next_weight=it.second;
25            if(dist[next_node]>distance+next_weight)
26            {
27                dist[next_node]=dist[node]+next_weight;
28                prior.push(make_pair(dist[next_node],next_node));
29            }
30        }
31    }
32    for(int i=0;i<n;i++)
33    {
34        cout<<dist[i]<<" ";
35    }
36}
37int main()
38{
39    int vertex,edges;
40    cout<<"ENTER THE NUMBER OF VERTEX AND EDGES:"<<endl;
41    cin>>vertex>>edges;
42    vector<pair<int,int>>adj[vertex];
43    int a,b,w;
44    cout<<"ENTER THE LINK AND THEN WEIGHT:"<<endl;
45    for(int i=0;i<edges;i++)
46    {
47        cin>>a>>b>>w;
48        addedge(adj,a,b,w);
49    }
50    int source;
51    cout<<"ENTER THE SOURCE NODE FROM WHICH YOU WANT TO CALCULATE THE SHORTEST DISTANCE:"<<endl;
52    cin>>source;
53    Dijkstra(adj,source,vertex);
54    return 0;
55}
56
Camry
05 Aug 2018
1//djikstra's algorithm using a weighted graph (STL)
2//code by Soumyadepp
3//insta: @soumyadepp
4//linkedinID: https://www.linkedin.com/in/soumyadeep-ghosh-90a1951b6/
5
6#include <bits/stdc++.h>
7#define ll long long
8using namespace std;
9
10//to find the closest unvisited vertex from the source
11//note that numbering of vertices starts from 1 here. Calculate accordingly
12ll minDist(ll dist[], ll n, bool visited[])
13{
14    ll min = INT_MAX;
15    ll minIndex = 0;
16    for (ll i = 1; i <= n; i++)
17    {
18        if (!visited[i] && dist[i] <= min)
19        {
20            min = dist[i];
21            minIndex = i;
22        }
23    }
24    return minIndex;
25}
26
27//djikstra's algorithm for single source shortest path
28void djikstra(vector<pair<ll, ll>> *g, ll n, ll src)
29{
30    bool visited[n + 1];
31    ll dist[n + 1];
32    for (ll i = 0; i <= n; i++)
33    {
34        dist[i] = INT_MAX;
35        visited[i] = false;
36    }
37
38    dist[src] = 0;
39
40    for (ll i = 0; i < n - 1; i++)
41    {
42        ll u = minDist(dist, n, visited);
43        visited[u] = true;
44        for (ll v = 0; v < g[u].size(); v++)
45        {
46            if (dist[u] + g[u][v].second < dist[g[u][v].first])
47            {
48                dist[g[u][v].first] = dist[u] + g[u][v].second;
49            }
50        }
51    }
52    cout << "VERTEX : DISTANCE" << endl;
53    for (ll i = 1; i <= n; i++)
54    {
55        if (dist[i] != INT_MAX)
56            cout << i << "         " << dist[i] << endl;
57        else
58            cout << i << "         "
59                 << "not reachable" << endl;
60    }
61    cout << endl;
62}
63
64int main()
65{
66    //to store the adjacency list which also contains the weight
67    vector<pair<ll, ll>> *graph;
68    ll n, e, x, y, w, src;
69    cout << "Enter number of vertices and edges in the graph" << endl;
70    cin >> n >> e;
71    graph = new vector<pair<ll, ll>>[n + 1];
72    cout << "Enter edges and weight" << endl;
73    for (ll i = 0; i < e; i++)
74    {
75        cin >> x >> y >> w;
76        //checking for invalid edges and negative weights.
77        if (x <= 0 || y <= 0 || w <= 0)
78        {
79            cout << "Invalid parameters. Exiting" << endl;
80            exit(-1);
81        }
82        graph[x].push_back(make_pair(y, w));
83        graph[y].push_back(make_pair(x, w));
84    }
85    cout << "Enter source from which you want to find shortest paths" << endl;
86    cin >> src;
87    if (src >= 1 && src <= n)
88        djikstra(graph, n, src);
89    else
90        cout << "Please enter a valid vertex as the source" << endl;
91    return 0;
92}
93
94//time complexity : O(ElogV)
95//space complexity: O(V)
96
Juan Esteban
09 May 2019
1
2# Providing the graph
3n = int(input("Enter the number of vertices of the graph"))
4
5# using adjacency matrix representation 
6vertices = [[0, 0, 1, 1, 0, 0, 0],
7            [0, 0, 1, 0, 0, 1, 0],
8            [1, 1, 0, 1, 1, 0, 0],
9            [1, 0, 1, 0, 0, 0, 1],
10            [0, 0, 1, 0, 0, 1, 0],
11            [0, 1, 0, 0, 1, 0, 1],
12            [0, 0, 0, 1, 0, 1, 0]]
13
14edges = [[0, 0, 1, 2, 0, 0, 0],
15         [0, 0, 2, 0, 0, 3, 0],
16         [1, 2, 0, 1, 3, 0, 0],
17         [2, 0, 1, 0, 0, 0, 1],
18         [0, 0, 3, 0, 0, 2, 0],
19         [0, 3, 0, 0, 2, 0, 1],
20         [0, 0, 0, 1, 0, 1, 0]]
21
22# Find which vertex is to be visited next
23def to_be_visited():
24    global visited_and_distance
25    v = -10
26    for index in range(num_of_vertices):
27        if visited_and_distance[index][0] == 0 \
28            and (v < 0 or visited_and_distance[index][1] <=
29                 visited_and_distance[v][1]):
30            v = index
31    return v
32
33
34num_of_vertices = len(vertices[0])
35
36visited_and_distance = [[0, 0]]
37for i in range(num_of_vertices-1):
38    visited_and_distance.append([0, sys.maxsize])
39
40for vertex in range(num_of_vertices):
41
42    # Find next vertex to be visited
43    to_visit = to_be_visited()
44    for neighbor_index in range(num_of_vertices):
45
46        # Updating new distances
47        if vertices[to_visit][neighbor_index] == 1 and 
48                visited_and_distance[neighbor_index][0] == 0:
49            new_distance = visited_and_distance[to_visit][1] 
50                + edges[to_visit][neighbor_index]
51            if visited_and_distance[neighbor_index][1] > new_distance:
52                visited_and_distance[neighbor_index][1] = new_distance
53        
54        visited_and_distance[to_visit][0] = 1
55
56i = 0
57
58# Printing the distance
59for distance in visited_and_distance:
60    print("Distance of ", chr(ord('a') + i),
61          " from source vertex: ", distance[1])
62    i = i + 1
Maureen
24 Apr 2017
1function Dijkstra(Graph, source):
2       dist[source]  := 0                     // Distance from source to source is set to 0
3       for each vertex v in Graph:            // Initializations
4           if v ≠ source
5               dist[v]  := infinity           // Unknown distance function from source to each node set to infinity
6           add v to Q                         // All nodes initially in Q
7
8      while Q is not empty:                  // The main loop
9          v := vertex in Q with min dist[v]  // In the first run-through, this vertex is the source node
10          remove v from Q 
11
12          for each neighbor u of v:           // where neighbor u has not yet been removed from Q.
13              alt := dist[v] + length(v, u)
14              if alt < dist[u]:               // A shorter path to u has been found
15                  dist[u]  := alt            // Update distance of u 
16
17      return dist[]
18  end function
19
Andrea
29 Sep 2017
1import sys
2
3class Vertex:
4    def __init__(self, node):
5        self.id = node
6        self.adjacent = {}
7        # Set distance to infinity for all nodes
8        self.distance = sys.maxint
9        # Mark all nodes unvisited        
10        self.visited = False  
11        # Predecessor
12        self.previous = None
13
14    def add_neighbor(self, neighbor, weight=0):
15        self.adjacent[neighbor] = weight
16
17    def get_connections(self):
18        return self.adjacent.keys()  
19
20    def get_id(self):
21        return self.id
22
23    def get_weight(self, neighbor):
24        return self.adjacent[neighbor]
25
26    def set_distance(self, dist):
27        self.distance = dist
28
29    def get_distance(self):
30        return self.distance
31
32    def set_previous(self, prev):
33        self.previous = prev
34
35    def set_visited(self):
36        self.visited = True
37
38    def __str__(self):
39        return str(self.id) + ' adjacent: ' + str([x.id for x in self.adjacent])
40
41class Graph:
42    def __init__(self):
43        self.vert_dict = {}
44        self.num_vertices = 0
45
46    def __iter__(self):
47        return iter(self.vert_dict.values())
48
49    def add_vertex(self, node):
50        self.num_vertices = self.num_vertices + 1
51        new_vertex = Vertex(node)
52        self.vert_dict[node] = new_vertex
53        return new_vertex
54
55    def get_vertex(self, n):
56        if n in self.vert_dict:
57            return self.vert_dict[n]
58        else:
59            return None
60
61    def add_edge(self, frm, to, cost = 0):
62        if frm not in self.vert_dict:
63            self.add_vertex(frm)
64        if to not in self.vert_dict:
65            self.add_vertex(to)
66
67        self.vert_dict[frm].add_neighbor(self.vert_dict[to], cost)
68        self.vert_dict[to].add_neighbor(self.vert_dict[frm], cost)
69
70    def get_vertices(self):
71        return self.vert_dict.keys()
72
73    def set_previous(self, current):
74        self.previous = current
75
76    def get_previous(self, current):
77        return self.previous
78
79def shortest(v, path):
80    ''' make shortest path from v.previous'''
81    if v.previous:
82        path.append(v.previous.get_id())
83        shortest(v.previous, path)
84    return
85
86import heapq
87
88def dijkstra(aGraph, start, target):
89    print '''Dijkstra's shortest path'''
90    # Set the distance for the start node to zero 
91    start.set_distance(0)
92
93    # Put tuple pair into the priority queue
94    unvisited_queue = [(v.get_distance(),v) for v in aGraph]
95    heapq.heapify(unvisited_queue)
96
97    while len(unvisited_queue):
98        # Pops a vertex with the smallest distance 
99        uv = heapq.heappop(unvisited_queue)
100        current = uv[1]
101        current.set_visited()
102
103        #for next in v.adjacent:
104        for next in current.adjacent:
105            # if visited, skip
106            if next.visited:
107                continue
108            new_dist = current.get_distance() + current.get_weight(next)
109            
110            if new_dist < next.get_distance():
111                next.set_distance(new_dist)
112                next.set_previous(current)
113                print 'updated : current = %s next = %s new_dist = %s' \
114                        %(current.get_id(), next.get_id(), next.get_distance())
115            else:
116                print 'not updated : current = %s next = %s new_dist = %s' \
117                        %(current.get_id(), next.get_id(), next.get_distance())
118
119        # Rebuild heap
120        # 1. Pop every item
121        while len(unvisited_queue):
122            heapq.heappop(unvisited_queue)
123        # 2. Put all vertices not visited into the queue
124        unvisited_queue = [(v.get_distance(),v) for v in aGraph if not v.visited]
125        heapq.heapify(unvisited_queue)
126    
127if __name__ == '__main__':
128
129    g = Graph()
130
131    g.add_vertex('a')
132    g.add_vertex('b')
133    g.add_vertex('c')
134    g.add_vertex('d')
135    g.add_vertex('e')
136    g.add_vertex('f')
137
138    g.add_edge('a', 'b', 7)  
139    g.add_edge('a', 'c', 9)
140    g.add_edge('a', 'f', 14)
141    g.add_edge('b', 'c', 10)
142    g.add_edge('b', 'd', 15)
143    g.add_edge('c', 'd', 11)
144    g.add_edge('c', 'f', 2)
145    g.add_edge('d', 'e', 6)
146    g.add_edge('e', 'f', 9)
147
148    print 'Graph data:'
149    for v in g:
150        for w in v.get_connections():
151            vid = v.get_id()
152            wid = w.get_id()
153            print '( %s , %s, %3d)'  % ( vid, wid, v.get_weight(w))
154
155    dijkstra(g, g.get_vertex('a'), g.get_vertex('e')) 
156
157    target = g.get_vertex('e')
158    path = [target.get_id()]
159    shortest(target, path)
160    print 'The shortest path : %s' %(path[::-1])
161
queries leading to this page
dijkstra algorithms havashow working of dijkstra algorithmdijkastra algorithm dijkstra 27s algorithm where we can 27t use dijkstra e2 80 99s algorithmhow to apply dijkstra algorithmdijkstra 27s algorithm explanationdijkstra 27s algorithm how can dijkstra 27s algorithm be implementedapply dijkstra 27s algorithmdijkstra pythondijkstra 27s algorithm data structuredijktra 27s algorithm python implementation dijkstra e2 80 99s algorithm is the an example of where is dijkstra algorithm useddijkstras algorithm mohammedalgorithm dijkstra pythondijkstra 27s algorithm geekswhat is the other name of dijkstra algorithm 3fwork of dijkstra 27s algorithmwhat is a dijkstra algorithmdijkstra shortest dijkstra e2 80 99s algorithm javawhat is dijkstra fordijkstra 27s algorithmapiusing dijkstra 27s algorithm codepurpose of dijkstra 27s algorithmdijkstara algorithm finding dijkstra in pythondijkshtra algorithmdijkstra 27s pythondijkstra 27s algorithm pythondijkstra 27s algdijkstra algorithm in o 28m 29dijkstra algorithm explanationdijkstra algoritmodijkstra 27s algorithm python youthibedijkstra 27s algorithm a to z python a c b d zdijkstra 27s algorithm in javadijkstra algorithm pythdijksta 27s algorithm using pythodijkstra algorithmdijkstra 27s algorithm nodejdijkstra 27s algorithm 5b63 5ddijkstra algoritmedijkstra algorithm used for how to code dijkstra 27s algorithmdijkstra 27s algorithm python implementation as a functiondijkstra 27a algorithmdijkstra 27sdijkstra algorithm implementation in javadijkstra algorithm uses whatimplementing dijkstra algorithm in pythondijkstra algoritmdescribe how dijkstra 27s algorithmdijkstra algorithm algorithm pythonalgo dijkstra pythonwhat is dijkstradijkstra algorithmus javadijkstra algorithm wikiidijkstra algorithmus pythondijkstras algorithm pythondijkstra 27s algorithm o notationdijkstra algorithm implementation pythonimplementation of dijkstra 27s algorithm in pythonpython dijkstra 27s algorithmdijkstra python codedjikstra algorith python using sysdijkstra 27s algowhat is dijkstra algorithmhow does dijkstra algorithm work in is isdijkstra e2 80 99s algorithm dijkstra algorithjdijkstra algorithm worksdijkstra algorithm in pythondisjkstra 27s python dijkstra algorithm simpledijkstra 27s algorithm is a 2a algorithmdijkstra 27s algorithm uses which approachdijkstra 27s algorithm in pythondijkstra algorithm usesdijkstra algorithm applicationdijkstra 27s algorithm is used to finddoes dijkstra algorithm always work 3fhow does dijkstra algorithm workhow to use dijkstra algorithm javadijkstra python algorithmdijk algorithmdijkstradijkstra algorithm java implementationdijkshtras algorithmdijkstra algorithms with examplesdijkstra algorithm tdijkstra e2 80 99s algorithm python codewho is dijkstra 27sexample of dijkstra 27s algorithmdijkstra algorithm javais dijkstra 27s algorithm harddijkstra 27s algorithm simple examplediscuss the applications of dijkstra e2 80 99s algorithmedsger dijkstra algorithmdijkstra e2 80 99s algorithmdijkstra algorithm python implementation tutorialdijkstra e2 80 99s algorithm is used for dijkstra algorithm python easydijkstra algorithm in graphapply the steps of the dijkstra 27s algorithmdijkstra e2 80 99s algorithm meaningdijkstra e2 80 99s algorithm in pythondijkstra 27s algorithm vs a 2a algorithmdijkstra 27s algorithm usesdijkstra 27s algorithm with python dijkstra algorithmdijkstra algorithm python implementationdijkstra 27s algorithm runtimedijkstra python implementationdijkstra 27s algorithmpython dijkstra implementationexplanation of dijkstra 27s algorithm with examplealgorithm dijkstra javadijkstra algorithmusdijkstra 27s algorithm relaxtiondijkstra algorithmdijksrtra algorithmhow to implement dijkstra 27s algorithmwrite dijkstra 27s algorithmdijkstra 27s algorithm correctdijkstra 27s algorithm with exampledijkstra algorithm implementation in pythonexplain dijkstra algorithm 22dijkstra 27s algorithm is a 22 dijkstra 27s algorithm 2cdijkstra 27s algorithm is used for dijkstras algorithmdijkstra algorithm is also calleddijkstra algorithm wiki rosdijkstra algorithmus python geekswhat is dijkstra algorithm javadijkstra algorithm osdijsktra python source to destdijkstra 27s algorithm used fordijkstra 27s algorithm conceptdijkstraat algorithmdijkstra algorithdijkstra algoritmaimplementation details of dijkstra algorithmdijkstra 27s algorithm in aidijkstra algorithm in javadijkstra e2 80 99s algorithm explainedsimple dijkstra pythondijkstra algorithm pythondijkstra algorythm pythondijkstra e2 80 99s algorithm shortest distancemaken dijkstra 27s algorithmdijkstra algorithm explainedwhy dijkstra algorithm idjisktra pythondijksta 27s algorithmhow to make a dijkstra algorithmdijkstras algorithm examplepython dijkstra algorithm python exampledijkstra algorithm implementationdijkstra algorithm python demoalgorithm of dijkstra algorithmdijkstra algorithm implementation javapython djikstra algorithm python example dijkstradijkstra 27s algorithm codedijkstra e2 80 99s algorithm vs a 2adijkstra algorithm python codedoes dijkstra 27s algorithm always workusing which algorithm to implement dijkstra 27sdijkstra algorithmn in javajava dijkstra algorithmdijkshtra e2 80 99s algorithmhow dijkstra algorithm worksdijkstra e2 80 99s algorithm is based on design approach dijkstra algorithm applicationshow does dijkstra 27s algorithm workwhat type of algorithm is dijkstra 27s algorithmhow to do dijkstra 27s algorithm pythondijkstra algorithm is based ondijkstra 27s algorithm founderdijkstra algorthmdijkstra 27s algorithm 5cdijkstra 27s algorithm implementation in pythonimplement dijkstra 27s algorithmhow to implement the dijkstra algorithm in pythonwhat approach is being followed in dijkstra 27s algorithm 3fwhat is dijkstra used forwhat is dijkstra algorithm in is isdijkstras pythondijkstra on pythondisjkstras algorithmdijkstra algorithm the algrositsdijkstra 27s algorithm code explanationwhen to use dijkstra algorithmwhat is the other name of dijkstra algorithm 3f dijkstra algorith 2cmdijkstra algorithm with pythonis dijkstra a simple algorithmwhat is dijkstra 27s algorithmdijkstra algorithm workingdijkstra algorithm how does it workbetter algorithm of dijkstra 27s algorithmdijkstra 27s algorithm python implementationdijkstra 27s algorithm examplehow to do dijkstra e2 80 99s algorithmdijkstra algorithm definition and exampleexplanation of dijkstra 27s algorithmexplain dijkstra algorithm with examplewhat can you use dijkstra algorithm fordijkstra 27s algorithm implement usnig djangodijkstra algorithm with stateswhat is dijkshtra algorithmdijkstra algorithm definitiondijkstra algorithm exampledijkstra exampledijkstra 27s algorithm javadijkstra 27s algorithm apido you need to know dijkstra algorithmthe dijkstra algorithmdijkstra 27s algorithm is based ondijksta algorithmdijkstra algorithm originalimplementing dijkstra algorithm codedijkstra 27s algorithm implement usnig python djangodijkstra algorithmsdijkstra algowhat is the use of dijkstra 27s algorithmdijkstra algorithm based ondijkstras algorithmus exampledescribe dijkstra algorithm with examplewhat does dijkstra 27s algorithm returndijkstra 27s algorithm for a fully connected graph pythondijkstra algwhat does dijkstra 27s algorithm doimplementing dijkstra algorithmdijkstra algorithm implementation tutorial in pythondijkstra 27s algorithm python exampledijkstra 27s algorithm python3algorithmos dijkstradijkstra 27s algorithm on directeddijkstra algorithm example with solutiondijkstra en pythondescribe dijkstra algorithmdijkstra algorithimwhat is the other name of dijkstra 27s algorithm 3f 2adjikstra algorithm pythondijkstra 27s algorithm graphdijkstra 27s algorithm purposedijkstras algorithm usesdijkstra 27s algorithm mathsdoes dijkstra algorithm how dijkstra 27s algorithm worksexample dijkstra algorithmdijkstra algorithm in pyhtonndijkstra akgorithmthe dijkstra algorithm uses which algorithmic technique 3fhow to solve dijistras algorithm pythondijkstra 27s 2cdijkstra 27s algorithm stepsdijkstra algorithm algorithhm pythhonalgorithm of dijkstrahow to code dijkstra 27s algorithm in pythondijkistra algorithmwhy dijkstra algorithm dijkstra algorithm solution pythonuse of dijkstra algorithmjava dijkstra 27s algorithm implementationdjikstra 27s algorithmdijkstra algorithm algorithmimplementation of dijkstra 27s algorithm in javadijkstra 27s algorithdijkastra 27s algorithmdijkstra algorithm algorithhmpython dijkstrahow to do dijkstra 27s algorithmdijkstra algorithm in data structuredijkstra in pythondijkstra e2 80 99s shortest path algorithm python what dijkstra 27s algo doeswhy dijkstra 27s algorithm worksdijkstra 27s algorithm works on the basis of which algorithm 3fdijkstra e2 80 99s algorithm is based on design approach write down the dijkstra 27s algorithmdijkstra algorithm java codedijkstra algorithm graph dijkstra e2 80 99s algorithm explanationdijkstra 27s algorithm java codedijkstra 27s algorithm python codedijkstras algorithm wiki dikajkra algorithmdijkstra 27s algorithm definationdijkstra e2 80 99s algorithmdijkstra 27s algorithm codedwhy dijkstra algorithm is useddijkstra algorithm programhow to implement dijkstra 27s algorithm in javadijkstra python exampledijkstra 27s python exampledijkstra 27s algorithm vs a 2adijktras algorithmdijkstra algorithm pyhtonjava dijkstra 27s algorithmhow does dijkstra algorithm worksdijkstra e2 80 99s algorithm graphalgorithm dijkstradijkstra algorithm on undirected graph pythondijkstra algorithm uoldijkstra algorithm codedijkstra algordijkstra algorith 2csdijkstra algorithm java exampledijkstra 27s algorithmbwhat is dijkstras algorithmdijkstra e2 80 99s algorithm is based on dijktras algorithm exampleexplain dijkstra 27s algorithm in pythondijkstra e2 80 99s algorithm pythonhow to use dijkstra 27s algorithm in javapython dijkstra algorithmdijkstra e2 80 99s algorithm 27dijktra 27s algorithmhow to implement dijkstra 27s algorithm in pythondijkstra algorithmedijkstra e2 80 99s algorithm 3adijkstra algorithm data structurewhat is the other name of dijkstra algorithmalgorithme dijkstrahow to use dijkstra 27s algorithmwhat is the other name of dijkstra 27s algorithm 3fdijkstra 27s algoritmdijkstra algo exampledijkstra 27s algorithm code in pythondijkstra algorithmus javadijkstra e2 80 99s algorithm is the an example of about dijkstra algorithmdijkstra algorithm wikidijkstra algorithm is used fordijkstra 27s algorithm demodijkstras algorithm in javawrite the dijkstra e2 80 99s algorithmdijkstra 27s algorithm algorithm python librarydijkstra algorithm isdijkstra implementation pythondijkstra 27s algorithm python