Dijkstra¶

Dijkstra's Algorithm¶

Dijkstra's algorithm finds the shortest paths from a source node to all other nodes in a weighted graph with non-negative edge weights. This algorithm uses a priority queue to always select the node with the minimum tentative distance.

Input: A weighted graph with non-negative weights, and a source node s Output: Shortest distances from s to all other nodes

Pseudocode¶

// Initialize distances
vector<float> dist(n, INF);
dist[s] = 0;

priority_queue<pair<float, int>> pq;
pq.push({0, s});

while (!pq.empty()) {
    // Select node with minimum distance
    int u = pq.top().second;
    float d = -pq.top().first;
    pq.pop();

    if (d > dist[u]) continue;

    // Update distances to neighbors
    for (auto &[v, w] : adj[u]) {
        if (dist[v] > dist[u] + w) {
            dist[v] = dist[u] + w;
            pq.push({-dist[v], v});
        }
    }
}

struct Edge {
    int to;
    float weight;
};

vector<float> dijkstra(const vector<vector<Edge>> &adj, int s) {
    int n = adj.size();
    vector<float> dist(n, INF);
    dist[s] = 0;

    // Use min-heap (priority_queue as max-heap with negative weights)
    priority_queue<pair<float, int>> pq;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        d = -d;

        // Skip processed nodes
        if (d > dist[u]) continue;

        for (auto &[v, w] : adj[u]) {
            // Check if new path is better
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({-dist[v], v});
            }
        }
    }
    return dist;
}

Dijkstra's Algorithm¶

We define an array called \(dis\). During algorithm execution, \(dis_u\) represents the shortest path to vertex \(u\) where the previous vertex in the path has definitely been selected (selection will be explained later). Initially, all elements of the \(dis\) array are set to \(\infty\). First, we know \(dis_{sc} = 0\). Now we select \(sc\) and update the \(dis\) values of \(sc\)'s neighboring vertices.

In each step of the algorithm, from among the vertices not yet selected, we choose the vertex with the minimal \(dis\) value and name it \(v\).

We now prove that the length of the shortest path from \(sc\) to \(v\) is exactly the current value of \(dis_v\). For this proof, we use contradiction: assume there exists a shorter path (a path of length \(P\)). Take the last selected vertex in this path and call it \(last\) (it must exist since vertex \(sc\) is selected). Name the next vertex after \(last\) as \(u\) (this next vertex must also exist since the final vertex wasn't selected yet).

By contradiction assumption, the path length to \(v\) is less than \(dis_v\), and since edges have non-negative weights, the path length to \(u\) is also less than \(dis_v\). Since the previous vertex of \(u\) in the path was a selected vertex and the final distances of selected vertices are exactly their \(dis\) values, then \(dis_u\) at the time of selecting \(last\) was equal to the shortest path length to \(u\). Given that \(dis_u < P\) and \(P < dis_v\), we have \(dis_u < dis_v\), which contradicts the minimality of \(dis_v\) among current values. Therefore, our initial assumption is false and the proof holds.

Now that we've proven \(dis_v\) exactly equals the shortest path length to \(v\), we select it and then for all its neighbors like \(adj\) where the edge from \(v\) to \(adj\) has weight \(w\), we perform: \(dis_{adj} = min(dis_{adj}, dis_v + w)\). We continue this process until all vertices are selected.

1def order_analysis(graph):
2    # peymayesh graph va mohaseye order
3    order = len(graph.nodes())
4    # bazgasht ehsas has order
5    return order

Order Analysis¶

There are two main approaches to implement this algorithm.