ospf.cpp File Reference

#include <iostream>
#include <limits>
#include <queue>
#include <vector>

Go to the source code of this file.

Classes
struct	Edge

Functions
void	dijkstra (const std::vector< std::vector< Edge >> &graph, int source, std::vector< int > &distances, std::vector< int > &parents)
int	main ()

Variables
const int	INF = std::numeric_limits<int>::max()

Function Documentation

dijkstra()

void dijkstra	(	const std::vector< std::vector< Edge >> &	graph,
		int	source,
		std::vector< int > &	distances,
		std::vector< int > &	parents
	)

Definition at line 53 of file ospf.cpp.

                                       {
    int n = graph.size();
    distances.assign(n, INF);
    parents.assign(n, -1);
 
    distances[source] = 0;
    std::priority_queue<std::pair<int, int>,
                        std::vector<std::pair<int, int>>,
                        std::greater<std::pair<int, int>>>
        pq;
    pq.push(std::make_pair(0, source));
 
    while (!pq.empty()) {
        int current = pq.top().second;
        int distance = pq.top().first;
        pq.pop();
 
        if (distance > distances[current])
            continue;
 
        for (const Edge &edge : graph[current]) {
            int neighbor = edge.to;
            int new_distance = distance + edge.weight;
 
            if (new_distance < distances[neighbor]) {
                distances[neighbor] = new_distance;
                parents[neighbor] = current;
                pq.push(std::make_pair(new_distance, neighbor));
            }
        }
    }
}

References INF.

Referenced by main().

main()

int main

(

void

)

Definition at line 89 of file ospf.cpp.

           {
    int n = 4; // Number of nodes
    std::vector<std::vector<Edge>> graph(n);
 
    graph[0].push_back({1, 2});
    graph[0].push_back({2, 5});
    graph[1].push_back({2, 1});
    graph[1].push_back({3, 3});
    graph[2].push_back({3, 1});
 
    int source = 0;
    std::vector<int> distances, parents;
    dijkstra(graph, source, distances, parents);
 
    int destination = 3;
    std::cout << "Shortest distance from " << source << " to " << destination
              << ": " << distances[destination] << std::endl;
    std::cout << "Shortest path: ";
    for (int node = destination; node != -1; node = parents[node])
        std::cout << node << " ";
    std::cout << std::endl;
 
    return 0;
}

References dijkstra().

Variable Documentation

INF

const int INF = std::numeric_limits<int>::max()

Definition at line 44 of file ospf.cpp.

Referenced by dijkstra().