Scribd
Upload
16 views

Exp 10

Uploaded by

papu varsha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
16 views

Exp 10

Uploaded by

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

DATE Ex.

NO: 10: Shortest Path Algorithms (Dijkstra's algorithm,


Bellman Ford Algorithm)

AIM:

To write a C++ program to implement Shortest Path Algorithm using Dijkstra


Algorithm.

ALGORITHM :

1. Initialization of all nodes with distance "infinite"; initialization of the starting node
with 0.

2. Marking of the distance of the starting node as permanent, all other distances as
temporarily.
3. Setting of starting node as active. Calculation of the temporary distances of all
neighbor nodes of the active node by summing up its distance with the weights of
the edges.
4. If such a calculated distance of a node is smaller as the current one, update the
distance and set the current node as antecessor.
5. This step is also called update and is Dijkstra's central idea.

6. Setting of the node with the minimal temporary distance as active.

7. Mark its distance as permanent. Repeating of steps 4 to 7 until there aren't any
nodes left with a permanent distance, which neighbors still have temporary
distance
PROGRAM:

#include <iostream>
using namespace std;
#include <limits.h>
#define V 9
int minDistance(int dist[], bool sptSet[])
{
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
void printSolution(int dist[])
{
cout <<"Vertex \t Distance from Source" << endl;
for (int i = 0; i < V; i++)
cout << i << " \t\t"<<dist[i]<< endl;
}
void dijkstra(int graph[V][V], int src)
{
int dist[V];
bool sptSet[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX,sptSet[i] = false;
dist[src] = 0;
for (int count = 0; count < V - 1; count++)
{
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] )
dist[v] = dist[u] + graph[u][v];
}
printSolution(dist);
}
int main()
{
dijkstra(graph, 0);
return 0;
}
OUTPUT :

Vertex Distance from Source

0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14

RESULT:
Thus the C++ program Shortest Path Algorithm using Dijkstras algorithm was written,
executed and verified successfully.
10 B: BELLMANFORD ALGORITHM
AIM:

To write a C++ program to implement Shortest Path Algorithm using Bellman ford
Algorithm.

ALGORITHM :

1. Start with the weighted graph .

2. Choose the starting vertex and assign infinity path values to all other vertex .

3. Visit each edge and relax the path distance if they are inaccurate .

4. We need to do this V times because in the worst case the vertex path length might
need to be readjusted V times .
5. Notice how the vertex at the top right corner had its path length adjusted .

6. After all vertices have their path lengths we check if a negative cycle is present.
PROGRAM:
#include <bits/stdc++.h>
struct Edge
{
int src, dest, weight;
};
struct Graph
{
int V, E;
struct Edge* edge;
};
struct Graph* createGraph(int V, int E)
{
struct Graph* graph = new Graph;
graph->V = V;
graph->E = E;64
graph->edge = new Edge[E];
return graph;
}
void printArr(int dist[], int n)
{
printf("Vertex Distance from Source\n");
for (int i = 0; i < n; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}
void BellmanFord(struct Graph* graph, int src)
{
int V = graph->V;
int E = graph->E;
int dist[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;
for (int i = 1; i <= V - 1; i++)
{
for (int j = 0; j < E; j++)
{
int u = graph->edge[j].src;
int v = graph->edge[j].dest;
int weight = graph->edge[j].weight;
if (dist[u] != INT_MAX
&& dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
for (int i = 0; i < E; i++)
{
int u = graph->edge[i].src;
int v = graph->edge[i].dest;
int weight = graph->edge[i].weight;

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


{
printf("Graph contains negative weight cycle");
return;
}
}
printArr(dist, V);
return;
}
int main()
{
int V = 5;
int E = 8;
struct Graph* graph = createGraph(V, E);
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = -1;
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 4;
graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 3;
graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 2;
graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 2;
graph->edge[5].src = 3;
graph->edge[5].dest = 2;
graph->edge[5].weight = 5;
graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1;
graph->edge[7].src = 4;
graph->edge[7].dest = 3;
graph->edge[7].weight = -3;
BellmanFord(graph, 0);
return 0;
}

OUTPUT :
Vertex Distance from Source
0 0
1 -1
2 2
3 -2
4 1

RESULT:
Thus the C++ program Shortest Path Algorithm using Bellman ford algorithm was written,
executed and verified successfully.

You might also like