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});
            }
        }
    }
}