Scribd
Upload
28 views4 pages

Dijikstra

The document contains two C++ implementations of graph algorithms: Dijkstra's algorithm and the Bellman-Ford algorithm. Dijkstra's algorithm finds the shortest paths from a source vertex to all other vertices in a weighted graph using a priority queue, while the Bellman-Ford algorithm also finds shortest paths but can handle graphs with negative weight edges and checks for negative weight cycles. Both algorithms output the shortest distances from the source vertex to all other vertices.

Uploaded by

omkarshivajirao
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
28 views4 pages

Dijikstra

The document contains two C++ implementations of graph algorithms: Dijkstra's algorithm and the Bellman-Ford algorithm. Dijkstra's algorithm finds the shortest paths from a source vertex to all other vertices in a weighted graph using a priority queue, while the Bellman-Ford algorithm also finds shortest paths but can handle graphs with negative weight edges and checks for negative weight cycles. Both algorithms output the shortest distances from the source vertex to all other vertices.

Uploaded by

omkarshivajirao
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

A

#include <iostream>

#include <vector>

#include <queue>

#include <climits>

using namespace std;

void dijkstra(int src, int n, vector<vector<pair<int, int>>>& graph) {

vector<int> dist(n, INT_MAX);

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

dist[src] = 0;

pq.push({0, src});

while (!pq.empty()) {

auto [d, u] = pq.top(); pq.pop();

if (d > dist[u]) continue;

for (auto [v, w] : graph[u]) {

if (dist[u] + w < dist[v]) {

dist[v] = dist[u] + w;

pq.push({dist[v], v});

cout << "Dijkstra Shortest Distances:\n";

for (int i = 0; i < n; ++i) {

cout << "Vertex " << i << " -> Distance " << dist[i] << endl;
}

int main() {

int n = 5;

vector<vector<pair<int, int>>> graph(n);

graph[0].push_back({1, 10});

graph[0].push_back({4, 3});

graph[1].push_back({2, 2});

graph[2].push_back({3, 9});

graph[4].push_back({1, 1});

graph[4].push_back({2, 4});

dijkstra(0, n, graph);

return 0;

#include <iostream>

#include <vector>

#include <climits>

using namespace std;

void bellmanFord(int src, int n, vector<vector<int>>& edges) {

vector<int> dist(n, INT_MAX);

dist[src] = 0;

for (int i = 1; i < n; ++i) { // Relax all edges V-1 times


for (auto& edge : edges) {

int u = edge[0], v = edge[1], w = edge[2];

if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {

dist[v] = dist[u] + w;

// Check for negative weight cycles

for (auto& edge : edges) {

int u = edge[0], v = edge[1], w = edge[2];

if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {

cout << "Graph contains a negative weight cycle\n";

return;

cout << "Bellman-Ford Shortest Distances:\n";

for (int i = 0; i < n; ++i) {

cout << "Vertex " << i << " -> Distance " << dist[i] << endl;

int main() {

int n = 5;

vector<vector<int>> edges = {

{0, 1, 10}, {0, 4, 3}, {1, 2, 2}, {2, 3, 9}, {4, 1, 1}, {4, 2, 4}

};

bellmanFord(0, n, edges);
return 0;

You might also like