Dijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms.
You are encouraged to solve this task according to the task description, using any language you may know.
For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex.
For example, if the vertices of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between one city and all other cities. As a result, the shortest path first is widely used in network routing protocols, most notably IS-IS and OSPF (Open Shortest Path First).
Important note: The inputs to Dijkstra's algorithm are a directed and weighted graph consisting of 2 or more nodes, generally represented by an adjacency matrix or list, and a start node. A destination node is not specified. The output is a set of edges depicting the shortest path to each destination node.
For the example we start:
a->b,cost=7,lastNode=a; a->c,cost=9,lastNode=a; a->d,cost=NA,lastNode=a; a->e,cost=NA,lastNode=a; a->f,cost=14,lastNode=a The lowest cost is a->b so we add a->b to the output. There is a connection from b->d so we update our input to a->c,cost=9,lastNode=a; a->d,cost=22,lastNode=b; a->e,cost=NA,lastNode=a; a->f,cost=14,lastNode=a The lowest cost is a->c so we add a->c to the output. Paths to d and f are cheaper via c so we update our input to a->d,cost=20,lastNode=c; a->e,cost=NA,lastNode=a; a->f,cost=11,lastNode=c The lowest cost is a->f so we add c->f to the output. We update our input to a->d,cost=20,lastNode=c; a->e,cost=NA,lastNode=a The lowest cost is a->d so we add c->d to the output. There is a connection from d->e so we update our input to a->e,cost=26,lastNode=d Which just leaves adding d->e to the output. The output should now be [d->e;c->d;c->f;a->c;a->b]
- Task
- Implement a version of Dijkstra's algorithm that outputs a set of edges depicting the shortest path to each reachable node from an origin.
- Run your program with the following directed graph starting at node a.
- Write a program which interprets the output from the above and use it to output the shortest path from node a to nodes e and f .
| Number | Name |
|---|---|
| 1 | a |
| 2 | b |
| 3 | c |
| 4 | d |
| 5 | e |
| 6 | f |
| Start | End | Cost |
|---|---|---|
| a | b | 7 |
| a | c | 9 |
| a | f | 14 |
| b | c | 10 |
| b | d | 15 |
| c | d | 11 |
| c | f | 2 |
| d | e | 6 |
| e | f | 9 |
You can use numbers or names to identify vertices in your program.
- See also
ALGOL 68
File: prelude_dijkstras_algorithm.a68<lang algol68># -*- coding: utf-8 -*- #
COMMENT REQUIRED BY "prelude_dijkstras_algorithm.a68" CO
MODE ROUTELEN = ~; ROUTELEN route len infinity = max ~; PROC route len add = (VERTEX v, ROUTE r)ROUTELEN: route len OF v + route len OF r; # or MAX(v,r) # MODE VERTEXPAYLOAD = ~; PROC dijkstra fix value error = (STRING msg)BOOL: (put(stand error, (msg, new line)); FALSE);
- PROVIDES:#
- VERTEX*=~* #
- ROUTE*=~* #
- vertex route*=~* #
END COMMENT
MODE VALVERTEX = STRUCT(
ROUTELEN route len, FLEX[0]ROUTE route, ROUTE shortest route, VERTEXPAYLOAD vertex data
);
MODE VERTEX = REF VALVERTEX; MODE VERTEXYIELD = PROC(VERTEX)VOID; # used to "generate" VERTEX path # PRIO INIT = 1; # The same PRIOrity as +:= etc # OP INIT = (VERTEX self, VERTEXPAYLOAD vertex data)VERTEX:
self := (route len infinity, (), NIL, vertex data);
- It may be faster to preallocate "queue", rather then grow a FLEX #
OP +:= = (REF FLEX[]VERTEX in list, VERTEX rhs)REF FLEX[]VERTEX: (
[UPB in list+1]VERTEX out list; out list[:UPB in list] := in list; out list[UPB out list] := rhs; in list := out list # EXIT #
);
MODE VALROUTE = STRUCT(VERTEX from, to, ROUTELEN route len#, ROUTEPAYLOAD#); MODE ROUTE = REF VALROUTE;
OP +:= = (REF FLEX[]ROUTE in list, ROUTE rhs)REF FLEX[]ROUTE: (
[UPB in list+1]ROUTE out list; out list[:UPB in list] := in list; out list[UPB out list] := rhs; in list := out list # EXIT #
);
MODE VERTEXROUTE = UNION(VERTEX, ROUTE); MODE VERTEXROUTEYIELD = PROC(VERTEXROUTE)VOID;
- Finally: now the strong typing is in place, the task code... #
PROC vertex route gen dijkstra = (
VERTEX source, target, REF[]VALROUTE route list, VERTEXROUTEYIELD yield )VOID:(
- initialise the route len for BOTH directions on each route #
FOR this TO UPB route list DO ROUTE route = route list[this]; route OF from OF route +:= route;
- assume route lens is the same in both directions, this i.e. NO A-B gradient NOR 1-way streets #
route OF to OF route +:= (HEAP VALROUTE := (to OF route, from OF route, route len OF route)) OD;
COMMENT
Algorithium Performance "about" O(n**2)...
Optimisations:
a) bound index in [lwb queue:UPB queue] for search
b) delay adding vertices until they are actually encountered
It may be faster to preallocate "queue" vertex list, rather then grow a FLEX
END COMMENT
PROC vertex gen nearest = (REF FLEX[]VERTEX queue, VERTEXYIELD yield)VOID: (
INT vertices done := 0, lwb queue := 1;
ROUTELEN shortest route len done := -route len infinity;
WHILE vertices done <= UPB queue ANDF shortest route len done NE route len infinity DO
ROUTELEN shortest route len := route len infinity;
- skip done elements: #
FOR this FROM lwb queue TO UPB queue DO
VERTEX this vertex := queue[this];
IF NOT(shortest route len done < route len OF this vertex) THEN
lwb queue := this; # remember for next time #
break
FI
OD;
break:
- find vertex with shortest path attached #
FOR this FROM lwb queue TO UPB queue DO VERTEX this vertex := queue[this];
IF shortest route len done < route len OF this vertex ANDF
route len OF this vertex < shortest route len THEN
shortest route len := route len OF this vertex FI
OD;
- update the other vertices with shortest path found #
FOR this FROM lwb queue TO UPB queue DO VERTEX this vertex := queue[this];
IF route len OF this vertex = shortest route len THEN
vertices done +:= 1; yield(this vertex) FI
OD;
shortest route len done := shortest route len
OD
);
route len OF target := 0; FLEX[0]VERTEX queue := target;
- FOR VERTEX this vertex IN # vertex gen nearest(queue#) DO (#,
- (VERTEX this vertex)VOID: (
FOR this TO UPB route OF this vertex DO ROUTE this route = (route OF this vertex)[this];
# If this vertex has not been encountered before, then add to queue #
IF route len OF to OF this route = route len infinity THEN queue +:= to OF this route FI;
ROUTELEN route len = route len add(this vertex, this route);
IF route len < route len OF to OF this route THEN
route len OF to OF this route := route len;
shortest route OF to OF this route := this route
FI
OD;
IF this vertex IS source THEN done FI
- OD#));
IF NOT dijkstra fix value error("no path found") THEN stop FI;
- Now: generate the result #
done: (
VERTEX this vertex := source;
WHILE
yield(this vertex);
ROUTE this route = shortest route OF this vertex;
# WHILE # this route ISNT ROUTE(NIL) DO
yield(this route);
this vertex := from OF this route
OD
)
);
SKIP</lang>File: test_dijkstras_algorithm.a68<lang algol68>#!/usr/bin/a68g --script #
- -*- coding: utf-8 -*- #
CO REQUIRED BY "prelude_dijkstras_algorithm.a68" CO
MODE ROUTELEN = INT, ROUTELEN route len infinity = max int, PROC route len add = (VERTEX v, ROUTE r)ROUTELEN: route len OF v + route len OF r; # or MAX(v,r) # MODE VERTEXPAYLOAD = STRING, PROC dijkstra fix value error = (STRING msg)BOOL: (put(stand error, (msg, new line)); FALSE);
- PROVIDES:#
- VERTEX*=~* #
- ROUTE*=~* #
- vertex route*=~* #
PR READ "prelude_dijkstras_algorithm.a68" PR;
FORMAT vertex data fmt = $g$;
main:(
INT upb graph = 6, upb route list = 9;
HEAP[upb graph]VALVERTEX graph;
- name the key vertices #
FOR this TO UPB graph DO graph[this] INIT STRING("abcdef"[this]) OD;
- declare some variables of the same name #
VERTEX a := graph[1], b := graph[2], c := graph[3],
d := graph[4], e := graph[5], f := graph[6];
- define the graph #
HEAP FLEX[upb route list]VALROUTE route list := (
(a, b, 7), (a, c, 9), (a, f, 14),
(b, c, 10), (b, d, 15),
(c, d, 11), (c, f, 2),
(d, e, 6),
(e, f, 9)
);
- FOR VERTEXROUTE vertex route IN # vertex route gen dijkstra(a, e, route list#) DO #,
- (VERTEXROUTE vertex route)VOID: (
CASE vertex route IN
(VERTEX vertex): printf((vertex data fmt, vertex data OF vertex)),
(ROUTE route): printf(($" --"g(0)"-> "$, route len OF route))
ESAC
- OD #));
print(new line)
- TODO: generate random 100000 VERTEX graph test case and test performance - important #
)</lang>Output:
a --9-> c --2-> f --9-> e
AutoHotkey
<lang AutoHotkey>Dijkstra(data, start){ nodes := [], dist := [], Distance := [], dist := [], prev := [], Q := [], min := "x" for each, line in StrSplit(data, "`n" , "`r") field := StrSplit(line,"`t"), nodes[field.1] := 1, nodes[field.2] := 1 , Distance[field.1,field.2] := field.3, Distance[field.2,field.1] := field.3 dist[start] := 0, prev[start] := ""
for node in nodes { if (node <> start) dist[node] := "x" , prev[node] := "" Q[node] := 1 }
while % ObjCount(Q) { u := MinDist(Q, dist).2 for node, val in Q if (node = u) { q.Remove(node) break }
for v, length in Distance[u] { alt := dist[u] + length if (alt < dist[v]) dist[v] := alt , prev[v] := u } } return [dist, prev] }
- -----------------------------------------------
MinDist(Q, dist){ for node , val in Q if A_Index=1 min := dist[node], minNode := node else min := min < dist[node] ? min : dist[node] , minNode := min < dist[node] ? minNode : node return [min,minNode] } ObjCount(Obj){ for key, val in Obj count := A_Index return count }</lang> Examples:<lang AutoHotkey>data = ( A B 7 A C 9 A F 14 B C 10 B D 15 C D 11 C F 2 D E 6 E F 9 )
nodes:=[], Distance := [] for each, line in StrSplit(data, "`n" , "`r")
field := StrSplit(line,"`t"), nodes[field.1] := 1, nodes[field.2] := 1 , Distance[field.1,field.2] := field.3 , Distance[field.2,field.1] := field.3
for node, v in nodes
nodeList .= (nodeList?"|":"") node (A_Index=1?"|":"")
Gui, add, Text,, From: Gui, add, Text, x200 yp, To: Gui, add, DDL, xs vFrom gSubmit, % nodeList Gui, add, DDL, x200 yp vTo gSubmit, % nodeList Gui, add, ListView, xs w340 r6, From|>|To|Distance Gui, add, Text, vT1 xs w340 r1 Gui, +AlwaysOnTop Gui, show Loop 4 LV_ModifyCol(A_Index, "80 Center")
Submit: Gui, Submit, NoHide GuiControl, , T1, % "" LV_Delete() if !(From && To) || (From = To)
return
res := Dijkstra(data, From) , xTo := xFrom := DirectFlight := "" , origin := to GuiControl, , T1, no routing found if !res[1, To] ; no possible route
return
Routing: Loop % objCount(nodes)
for xTo , xFrom in res.2
if (xTo = To)
{
LV_Insert(1,"", xFrom, ">" , xTo, Distance[xFrom , xTo]), To := xFrom
if (xFrom = From)
break, Routing
}
GuiControl, , T1, % "Total distance = " res.1[origin] . DirectFlight return
esc:: GuiClose: ExitApp return</lang>
Outputs:
A > C 9 C > F 2 F > E 9 Total distance = 20
C
The priority queue is implemented as a binary heap. The heap stores an index into its data array, so it can quickly update the weight of an item already in it.
<lang c>#include <stdio.h>
- include <stdlib.h>
- include <limits.h>
typedef struct {
int vertex; int weight;
} edge_t;
typedef struct {
edge_t **edges; int edges_len; int edges_size; int dist; int prev; int visited;
} vertex_t;
typedef struct {
vertex_t **vertices; int vertices_len; int vertices_size;
} graph_t;
typedef struct {
int *data; int *prio; int *index; int len; int size;
} heap_t;
void add_vertex (graph_t *g, int i) {
if (g->vertices_size < i + 1) {
int size = g->vertices_size * 2 > i ? g->vertices_size * 2 : i + 4;
g->vertices = realloc(g->vertices, size * sizeof (vertex_t *));
for (int j = g->vertices_size; j < size; j++)
g->vertices[j] = NULL;
g->vertices_size = size;
}
if (!g->vertices[i]) {
g->vertices[i] = calloc(1, sizeof (vertex_t));
g->vertices_len++;
}
}
void add_edge (graph_t *g, int a, int b, int w) {
a = a - 'a';
b = b - 'a';
add_vertex(g, a);
add_vertex(g, b);
vertex_t *v = g->vertices[a];
if (v->edges_len >= v->edges_size) {
v->edges_size = v->edges_size ? v->edges_size * 2 : 4;
v->edges = realloc(v->edges, v->edges_size * sizeof (edge_t *));
}
edge_t *e = calloc(1, sizeof (edge_t));
e->vertex = b;
e->weight = w;
v->edges[v->edges_len++] = e;
}
heap_t *create_heap (int n) {
heap_t *h = calloc(1, sizeof (heap_t)); h->data = calloc(n + 1, sizeof (int)); h->prio = calloc(n + 1, sizeof (int)); h->index = calloc(n, sizeof (int)); return h;
}
void push_heap (heap_t *h, int v, int p) {
int i = h->index[v] == 0 ? ++h->len : h->index[v];
int j = i / 2;
while (i > 1) {
if (h->prio[j] < p)
break;
h->data[i] = h->data[j];
h->prio[i] = h->prio[j];
h->index[h->data[i]] = i;
i = j;
j = j / 2;
}
h->data[i] = v;
h->prio[i] = p;
h->index[v] = i;
}
int min (heap_t *h, int i, int j, int k) {
int m = i;
if (j <= h->len && h->prio[j] < h->prio[m])
m = j;
if (k <= h->len && h->prio[k] < h->prio[m])
m = k;
return m;
}
int pop_heap (heap_t *h) {
int v = h->data[1];
int i = 1;
while (1) {
int j = min(h, h->len, 2 * i, 2 * i + 1);
if (j == h->len)
break;
h->data[i] = h->data[j];
h->prio[i] = h->prio[j];
h->index[h->data[i]] = i;
i = j;
}
h->data[i] = h->data[h->len];
h->prio[i] = h->prio[h->len];
h->index[h->data[i]] = i;
h->len--;
return v;
}
void dijkstra (graph_t *g, int a, int b) {
int i, j;
a = a - 'a';
b = b - 'a';
for (i = 0; i < g->vertices_len; i++) {
vertex_t *v = g->vertices[i];
v->dist = INT_MAX;
v->prev = 0;
v->visited = 0;
}
vertex_t *v = g->vertices[a];
v->dist = 0;
heap_t *h = create_heap(g->vertices_len);
push_heap(h, a, v->dist);
while (h->len) {
i = pop_heap(h);
if (i == b)
break;
v = g->vertices[i];
v->visited = 1;
for (j = 0; j < v->edges_len; j++) {
edge_t *e = v->edges[j];
vertex_t *u = g->vertices[e->vertex];
if (!u->visited && v->dist + e->weight <= u->dist) {
u->prev = i;
u->dist = v->dist + e->weight;
push_heap(h, e->vertex, u->dist);
}
}
}
}
void print_path (graph_t *g, int i) {
int n, j;
vertex_t *v, *u;
i = i - 'a';
v = g->vertices[i];
if (v->dist == INT_MAX) {
printf("no path\n");
return;
}
for (n = 1, u = v; u->dist; u = g->vertices[u->prev], n++)
;
char *path = malloc(n);
path[n - 1] = 'a' + i;
for (j = 0, u = v; u->dist; u = g->vertices[u->prev], j++)
path[n - j - 2] = 'a' + u->prev;
printf("%d %.*s\n", v->dist, n, path);
}
int main () {
graph_t *g = calloc(1, sizeof (graph_t)); add_edge(g, 'a', 'b', 7); add_edge(g, 'a', 'c', 9); add_edge(g, 'a', 'f', 14); add_edge(g, 'b', 'c', 10); add_edge(g, 'b', 'd', 15); add_edge(g, 'c', 'd', 11); add_edge(g, 'c', 'f', 2); add_edge(g, 'd', 'e', 6); add_edge(g, 'e', 'f', 9); dijkstra(g, 'a', 'e'); print_path(g, 'e'); return 0;
}</lang>
output
26 acde
C++
(Modified from LiteratePrograms, which is MIT/X11 licensed.)
Solution follows Dijkstra's algorithm as described elsewhere. Data like min-distance, previous node, neighbors, are kept in separate data structures instead of part of the vertex. We number the vertexes starting from 0, and represent the graph using an adjacency list (vector whose i'th element is the vector of neighbors that vertex i has edges to) for simplicity.
For the priority queue of vertexes, we use a self-balancing binary search tree (std::set), which should bound time complexity by O(E log V). Although C++ has heaps, without knowing the index of an element it would take linear time to find it to re-order it for a changed weight. It is not easy to keep the index of vertexes in the heap because the heap operations are opaque without callbacks. On the other hand, using a self-balancing binary search tree is efficient because it has the same log(n) complexity for insertion and removal of the head element as a binary heap. In addition, a self-balancing binary search tree also allows us to find and remove any other element in log(n) time, allowing us to perform the decrease-key step in logarithmic time by removing and re-inserting.
We do not need to keep track of whether a vertex is "done" ("visited") as in the Wikipedia description, since re-reaching such a vertex will always fail the relaxation condition (when re-reaching a "done" vertex, the new distance will never be less than it was originally), so it will be skipped anyway.
The time complexity of this algorithm is O(E log V), as described on Wikipedia. Each vertex is added to the priority queue at most once (re-ordering doesn't count as adding), because once it's in the priority queue, we only re-order it, never add it again. And when it's popped from the priority queue, that means we already have the real minimum distance to this vertex, so the relaxation condition will always fail in the future for this vertex, and it will never be added to the priority queue again. Therefore, we will only pop each vertex at most once from the priority queue, and the size of the priority queue is bounded by V (the number of vertexes).
The outer loop executes once for each element popped from the priority queue, so it will execute at most once for each vertex, so at most V times. Each iteration of the outer loop executes one pop from the priority queue, which has time complexity O(log V). The inner loop executes at most once for each directed edge, since each directed edge has one originating vertex, and there is only at most one iteration of the outer loop for each vertex. Each iteration of the inner loop potentially performs one push or re-order on the priority queue (where re-order is a pop and a push), which has complexity O(log V). There is also the O(V) complexity for initializing the data structures. Combining these, we have a complexity of O(V log V + E log V), and assuming this is a connected graph, V <= E+1 = O(E), so we can write it as O(E log V).
<lang cpp>#include <iostream>
- include <vector>
- include <string>
- include <list>
- include <limits> // for numeric_limits
- include <set>
- include <utility> // for pair
- include <algorithm>
- include <iterator>
typedef int vertex_t;
typedef double weight_t;
const weight_t max_weight = std::numeric_limits<double>::infinity();
struct neighbor {
vertex_t target;
weight_t weight;
neighbor(vertex_t arg_target, weight_t arg_weight)
: target(arg_target), weight(arg_weight) { }
};
typedef std::vector<std::vector<neighbor> > adjacency_list_t;
void DijkstraComputePaths(vertex_t source,
const adjacency_list_t &adjacency_list,
std::vector<weight_t> &min_distance,
std::vector<vertex_t> &previous)
{
int n = adjacency_list.size(); min_distance.clear(); min_distance.resize(n, max_weight); min_distance[source] = 0; previous.clear(); previous.resize(n, -1); std::set<std::pair<weight_t, vertex_t> > vertex_queue; vertex_queue.insert(std::make_pair(min_distance[source], source));
while (!vertex_queue.empty())
{
weight_t dist = vertex_queue.begin()->first;
vertex_t u = vertex_queue.begin()->second;
vertex_queue.erase(vertex_queue.begin());
// Visit each edge exiting u
const std::vector<neighbor> &neighbors = adjacency_list[u];
for (std::vector<neighbor>::const_iterator neighbor_iter = neighbors.begin();
neighbor_iter != neighbors.end();
neighbor_iter++)
{
vertex_t v = neighbor_iter->target;
weight_t weight = neighbor_iter->weight;
weight_t distance_through_u = dist + weight;
if (distance_through_u < min_distance[v]) { vertex_queue.erase(std::make_pair(min_distance[v], v));
min_distance[v] = distance_through_u; previous[v] = u; vertex_queue.insert(std::make_pair(min_distance[v], v));
}
} }
}
std::list<vertex_t> DijkstraGetShortestPathTo(
vertex_t vertex, const std::vector<vertex_t> &previous)
{
std::list<vertex_t> path;
for ( ; vertex != -1; vertex = previous[vertex])
path.push_front(vertex);
return path;
}
int main()
{
// remember to insert edges both ways for an undirected graph adjacency_list_t adjacency_list(6); // 0 = a adjacency_list[0].push_back(neighbor(1, 7)); adjacency_list[0].push_back(neighbor(2, 9)); adjacency_list[0].push_back(neighbor(5, 14)); // 1 = b adjacency_list[1].push_back(neighbor(0, 7)); adjacency_list[1].push_back(neighbor(2, 10)); adjacency_list[1].push_back(neighbor(3, 15)); // 2 = c adjacency_list[2].push_back(neighbor(0, 9)); adjacency_list[2].push_back(neighbor(1, 10)); adjacency_list[2].push_back(neighbor(3, 11)); adjacency_list[2].push_back(neighbor(5, 2)); // 3 = d adjacency_list[3].push_back(neighbor(1, 15)); adjacency_list[3].push_back(neighbor(2, 11)); adjacency_list[3].push_back(neighbor(4, 6)); // 4 = e adjacency_list[4].push_back(neighbor(3, 6)); adjacency_list[4].push_back(neighbor(5, 9)); // 5 = f adjacency_list[5].push_back(neighbor(0, 14)); adjacency_list[5].push_back(neighbor(2, 2)); adjacency_list[5].push_back(neighbor(4, 9));
std::vector<weight_t> min_distance; std::vector<vertex_t> previous; DijkstraComputePaths(0, adjacency_list, min_distance, previous); std::cout << "Distance from 0 to 4: " << min_distance[4] << std::endl; std::list<vertex_t> path = DijkstraGetShortestPathTo(4, previous); std::cout << "Path : "; std::copy(path.begin(), path.end(), std::ostream_iterator<vertex_t>(std::cout, " ")); std::cout << std::endl;
return 0;
}</lang>
Note that it is possible to use C++ built-in heaps (or the abstract std::priority_queue datatype) to implement this without changing the time complexity. Although the previous section noted that, without knowing the position of the element in the heap, it would take linear time to search for it in order to re-order it, the trick here is that we can insert the new updated element (with the vertex and updated lower distance), and simply leave the old element (with the vertex and old higher distance) in the priority queue without removing it, thereby eliminating the need to find it.
Since we now leave multiple elements with the same vertex in the priority queue, in order to ensure we still only process a vertex's edges only once, we add a check when we retrieve an element from the priority queue, to check whether its distance is greater than the known minimum distance to that vertex. If this element is the most updated version for this vertex (i.e. the vertex's minimum distance has not been decreased since this element was added to the priority queue), then its distance must be equal to the current known minimum distance, since we only update the minimum distance in the decrease-key step. So if the element's distance is greater, we know that this is not the most updated version for this vertex -- i.e. we have already processed the edges for this vertex -- and we should ignore it.
The only downside to this strategy is that many old "garbage" elements will be left in the priority queue, increasing its size, and thus also increasing the time it takes to push and pop, as well as increasing the number of times we have to pop. However, we argue that the time complexity remains the same.
The main difference with the time complexity analysis for the previous algorithm is that here, we may add a vertex to the priority queue more than once. However, it is still true that the inner loop executes at most once for each directed edge. This is because in the outer loop, we added a check to ignore vertexes that we've already processed, so we will still only proceed down to the processing the edges at most once for each vertex. Therefore, the number of times that push is done on the priority queue (which happens at most once per iteration of the inner loop) is bounded by E, and the size of the priority queue is also bounded by E.
The number of times