The shortest path problem is about finding a path between 2 vertices in a graph such that the total sum of the weights of the edges is minimum.
Bellman Ford's Algorithm:
In a weighted network, Bellman Ford's technique is used to discover the shortest routes from the source vertex to all other vertices. It is based on the following concept: Because the shortest path cannot have a cycle, it has the most edges.
Implementation
vector <int> v [2000 + 10];
int dis [1000 + 10];
for(int i = 0; i < m + 2; i++){
v[i].clear();
dis[i] = 2e9;
}
for(int i = 0; i < m; i++){
scanf("%d%d%d", &from , &next , &weight);
v[i].push_back(from);
v[i].push_back(next);
v[i].push_back(weight);
}
dis[0] = 0;
for(int i = 0; i < n - 1; i++){
int j = 0;
while(v[j].size() != 0){
if(dis[ v[j][0] ] + v[j][2] < dis[ v[j][1] ] ){
dis[ v[j][1] ] = dis[ v[j][0] ] + v[j][2];
}
j++;
}
}
Dijkstra's Algorithm
The most frequent form of Dijkstra's method is to determine the shortest routes from the source vertex to all other vertices in the graph.
Implementation
#define SIZE 100000 + 1
vector<pair<int, int>> v[SIZE]; // each vertex has all the connected vertices with the edges weights
int dist[SIZE];
bool vis[SIZE];
void dijkstra()
{
// set the vertices distances as infinity
memset(vis, false, sizeof vis);
dist[1] = 0;
multiset<pair<int, int>> s;
s.insert({0, 1});
while (!s.empty())
{
pair<int, int> p = *s.begin();
s.erase(s.begin());
int x = p.s;
int wei = p.f;
if (vis[x])
continue;
vis[x] = true;
for (int i = 0; i < v[x].size(); i++)
{
int e = v[x][i].f;
int w = v[x][i].s;
if (dist[x] + w < dist[e])
{ // check if the next vertex distance could be minimized
dist[e] = dist[x] + w;
s.insert({dist[e], e});
}
}
}
}
0 Comments