dijkstra's algorithm

an algorithm that finds the minimum distances from a given "origin" vertex to all the other vertices in a weighted graph, in other words, it generates a shortest-path tree for a given vertex.
$\text{[math]}$

the method $\text{[math]}$ is the building block of dijkstra's algorithm, it checks whether the path we've taken to get to the vertex we're currently at is shorter than a past path we've taken (the length of the past path at that time would be stored in $\text{[math]}$ , $\text{[math]}$ being the distance array and $\text{[math]}$ being the vertex we've arrived at), and resets the value of $\text{[math]}$ and $\text{[math]}$ accordingly. in this note i refer to this as a relaxing step.

let $\text{[math]}$ be a non-negatively weighted graph. assume that dijkstra is being applied to $\text{[math]}$ starting at some vertex $\text{[math]}$ . at each step, for every vertex $\text{[math]}$ , if $\text{[math]}$ then in $\text{[math]}$ there exists a path $\text{[math]}$ from $\text{[math]}$ to $\text{[math]}$ and:

$\text{[math]}$
if $\text{[math]}$ then $\text{[math]}$ is the second-to-last vertex in the path $\text{[math]}$

let $\text{[math]}$ be a series of relaxing steps that were applied during the execution of the algorithm. the proof is done by induction on $\text{[math]}$ (index of relaxing steps)
base step (for $\text{[math]}$ ): before the application of $\text{[math]}$ , $\text{[math]}$ , and for every other vertex $\text{[math]}$ , $\text{[math]}$ and so the claim holds true (in this case)
[[blk:1673212044][induction step]]: induction hypothesis: assume the claim is true after the execution of $\text{[math]}$ , and let $\text{[math]}$ . for each vertex $\text{[math]}$ , $\text{[math]}$ doesnt change, and the claim follows trivially from the induction hypothesis. if $\text{[math]}$ is an empty relaxing step, the claim is also true for $\text{[math]}$ . assume $\text{[math]}$ isnt an empty step, in this case, after the relaxing step $\text{[math]}$ is executed, $\text{[math]}$ and $\text{[math]}$ , according to the induction hypothesis, there is a path from $\text{[math]}$ to $\text{[math]}$ whose length is $\text{[math]}$ and it follows that there is a path from $\text{[math]}$ to $\text{[math]}$ whose length is $\text{[math]}$ , and the last edge in that path is $\text{[math]}$ .

$\text{[math]}$ is true for all $\text{[math]}$ at each step of the dijkstra algorithm, if during one step $\text{[math]}$ , the value of $\text{[math]}$ stays the same and doesnt change again during the execution of the algorithm

according to lem-dijk-1, for each vertex $\text{[math]}$ and at each step of the algorithm, if $\text{[math]}$ , $\text{[math]}$ is the length of some path from $\text{[math]}$ to $\text{[math]}$ . from the code it follows that the value of $\text{[math]}$ changes only by the relaxing method, and so this value can only get smaller, the correctness of the entailment follows from the definition of $\text{[math]}$ being the minimal path from $\text{[math]}$ to $\text{[math]}$ .

let $\text{[math]}$ be a non-negatively weighted graph, and let $\text{[math]}$ be a minimal path in $\text{[math]}$ , then:

$\text{[math]}$ for each $\text{[math]}$
if executing a series of relaxing steps $\text{[math]}$ along $\text{[math]}$ , such that $\text{[math]}$ then $\text{[math]}$

note that the series of relaxing steps would be done in the written order, but between each two steps there might be more steps that get executed

proof for claim 1: we denote $\text{[math]}$ . $\text{[math]}$ for all $\text{[math]}$ and it follows that $\text{[math]}$ . every subpath of a minimal path is a minimal path and so $\text{[math]}$ for each $\text{[math]}$
proof for claim 2: left unwritten

main lemma for proof of correctness:
let $\text{[math]}$ be a non-negatively weighted graph. upon applying dijkstra to $\text{[math]}$ , starting at $\text{[math]}$ , each vertex $\text{[math]}$ , by the time it gets removed from $\text{[math]}$ , would have had its demands met.

the proof is by induction on the removal of vertices from $\text{[math]}$
base step: after the initialization $\text{[math]}$ and for each vertex $\text{[math]}$ , $\text{[math]}$ , its true that $\text{[math]}$ . the first vertex that gets removed from $\text{[math]}$ is $\text{[math]}$ . since the weights of all the edges arent negative, $\text{[math]}$ , and so $\text{[math]}$ meets the first demand. the second demand of the vertex is empty as it should be ( $\text{[math]}$ ).
[[blk:1673212044][induction step]]: induction hypothesis: assume the demands are met for each of the vertex that were removed from $\text{[math]}$ in the timestamps $\text{[math]}$ and let $\text{[math]}$ be the vertex that is removed from $\text{[math]}$ at the timestamp $\text{[math]}$ . we have to prove that at the timestamp $\text{[math]}$ the demands of the vertex $\text{[math]}$ are met. given that every vertex in $\text{[math]}$ is reachable from $\text{[math]}$ . let $\text{[math]}$ be a minimal path from $\text{[math]}$ to $\text{[math]}$ . assume that $\text{[math]}$ . let $\text{[math]}$ be the last vertex in $\text{[math]}$ that was removed from $\text{[math]}$ before $\text{[math]}$ . according to the induction hypothesis, by the time of removal of $\text{[math]}$ from $\text{[math]}$ , we know $\text{[math]}$ . right after, relaxing steps are applied from $\text{[math]}$ to its neighbors, one of which is $\text{[math]}$ . the path $\text{[math]}$ is minimal. according to lem-dijk-2, after the execution of this relaxing step, we know $\text{[math]}$ , consider the following cases:
case 1: $\text{[math]}$ , when $\text{[math]}$ is removed from $\text{[math]}$ , the algorithm applies a relaxing step to each of $\text{[math]}$ 's neighbors, one of which is $\text{[math]}$ , according to lem-dijk-2, after the execution of $\text{[math]}$ , we know $\text{[math]}$ and $\text{[math]}$ is the second-to-last vertex in the minimal path from $\text{[math]}$ to $\text{[math]}$ .
case 2: $\text{[math]}$ , this happens when $\text{[math]}$ is a minimal path from $\text{[math]}$ to $\text{[math]}$ , this might happen when the weights of the edges leading up to $\text{[math]}$ are 0, which would give other vertices the same distance from the origin as $\text{[math]}$ , and so the algorithm could choose to relax some edges before others, and the "natural" order of traversal could change, but because we know $\text{[math]}$ it follows that $\text{[math]}$ . let $\text{[math]}$ be the vertex that "discovers" $\text{[math]}$ . according to the code $\text{[math]}$ exists in $\text{[math]}$ before $\text{[math]}$ . according to the induction hypothesis the demands for $\text{[math]}$ would already have been met, it follows that after the last relaxing step the demands for $\text{[math]}$ would be met.

[[blk:1667592363][correctness]] of dijkstra:
assume dijkstra is applied to a non-negatively weighted graph $\text{[math]}$ and an origin vertex $\text{[math]}$ . the demands of every vertex $\text{[math]}$ are met. this follows from lem-dijk-3

the set of edges
$\text{[math]}$ forms a distance tree

for each vertex $\text{[math]}$ , in $\text{[math]}$ there is a path from the origin $\text{[math]}$ to $\text{[math]}$ . it follows that $\text{[math]}$ is connected. in $\text{[math]}$ there is exactly $\text{[math]}$ and so $\text{[math]}$ is a tree. we've already seen that for all $\text{[math]}$ , the only path in $\text{[math]}$ from $\text{[math]}$ to $\text{[math]}$ is a minimal path in $\text{[math]}$ , i.e. $\text{[math]}$

the cost of initialization (using $\text{[math]}$ ) is $\text{[math]}$
the main loop (in $\text{[math]}$ ) executes $\text{[math]}$ times, on each iteration it chooses a minimal vertex and improves on all of its neighbors, if $\text{[math]}$ isnt a directed graph, then during the relaxing step we test each edge twice, once in each direction. if $\text{[math]}$ is a directed graph, each edge is tested once. so the cost of all relaxing steps together is $\text{[math]}$ . picking the minimal vertex using the straightforward method also takes $\text{[math]}$ steps. the process of picking the minimal vertex is repeated $\text{[math]}$ times so the total cost is $\text{[math]}$
for non-dense graphs, we can improve the time complexity by turning $\text{[math]}$ into a min heap, picking a minimal vertex would take $\text{[math]}$ . the cost of all picks would be $\text{[math]}$ , on each of the $\text{[math]}$ relaxing steps we would need to do a correction in the heap, the cost of all corrections would be $\text{[math]}$ , so the total cost would be $\text{[math]}$

given a weighted graph $\text{[math]}$ that represents a town's junctions/roads
given $\text{[math]}$ is a subset of junctions with streetlights
given $\text{[math]}$ , propose an algorithm that given $\text{[math]}$ would find the length of the shortest paths from $\text{[math]}$ to each of the vertices in the graph, such that each path wouldnt contain more than 2 junctions with streetlights

$\text{[math]}$ complexity of this algorithm is $\text{[math]}$

assume we're given a graph $\text{[math]}$ with real weights (allows negative weights) and we wanted to find the distances between the vertices, we can do the following

find the edge $\text{[math]}$ that has the lowest weight in $\text{[math]}$
if $\text{[math]}$ , just apply $\text{[math]}$
otherwise, build a new graph $\text{[math]}$ , such that $\text{[math]}$ and $\text{[math]}$
run $\text{[math]}$ , which would be a modified version of dijkstra that also stores the actual length (number of edges) of the shortest path between $\text{[math]}$ and any other vertex $\text{[math]}$
return $\text{[math]}$ , such that $\text{[math]}$ is the output from the modified dijkstra algorithm, and $\text{[math]}$ is the number of edges in the shortest path between $\text{[math]}$ and $\text{[math]}$ .

given an undirected graph $\text{[math]}$ , let $\text{[math]}$ , we define $\text{[math]}$ , we want to write an algorithm that find $\text{[math]}$ .

define a new graph $\text{[math]}$
run $\text{[math]}$
return $\text{[math]}$

let $\text{[math]}$ be a directed non-negatively weighted graph. a vertex is called origin iff $\text{[math]}$ and pit iff $\text{[math]}$ . for every vertex we define the length of the shortest path that starts from some origin, goes through $\text{[math]}$ and ends in some pit as $\text{[math]}$
propose an algorithm that finds $\text{[math]}$ for each vertex in the graph

define a graph $\text{[math]}$ such that $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$
run $\text{[math]}$
define a graph $\text{[math]}$ such that $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$
run $\text{[math]}$
return $\text{[math]}$ for each $\text{[math]}$