Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
3.1 kB
3
Indexable
Never
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>



// function to print the final result
void print(int n, int src, int dist[])
{
        
        
        int min, ind, i;
        min = INT_MAX ;
        
        for (i = 0; i < n; i++) {
        
                if((dist[i] < min) && (i != src)) {
                        min = dist[i];
                        ind = i;
                        
                        
                }       
                
                
        }
        
        
        printf("\nMayor in City %d captures first\n", ind);
                
                
}

// function to find minimum distance
int mD(int n, int dt[], bool s[])
{
        
        int mn = INT_MAX, m_in;

        for (int i = 0; i < n; i++)
                if (dt[i] <= mn && s[i] == false) {
                        mn = dt[i]; 
                        m_in = i;
                
                }
                        

        return m_in;
}


// dijkstra algorithm to find shortest paths from the source each of the vertex.

void Dij(int n, int G[n][n], int src)
{
        int dt[n]; 

        bool s[n];

        
        for (int i = 0; i < n; i++) {
                s[i] = false;
                
                dt[i] = INT_MAX; 
        
        }
                

        
        dt[src] = 0;

        
        for (int c = 0; c < (n-1) ; ++c) {
                
                int z = mD(n, dt, s);

                
                s[z] = true;

                
                for (int v = 0; v < n; v++)

                        
                        if (!s[v] && G[z][v] && dt[z] != INT_MAX
                                && dt[z] + G[z][v] < dt[v])
                                dt[v] = dt[z] + G[z][v];
        }

        
        print(n, src, dt);
}


int main()           // main function
{
        
        int n, r, m, val, ind_end, ind;
        printf("\nn:");
        scanf("%d", &n);   // console input for n
        printf("r:");
        scanf("%d", &r);   // console input for r
        
        int edg[r][3];     // input for edges
        for (int i=0; i<r; i++) {
                scanf("%d %d %d", &edg[i][0], &edg[i][1], &edg[i][2]);
        
        }
        
        printf("m:");
        scanf("%d", &m);   // input for source      
        
        
        int graph[n][n];
        
        for(int i=0; i<n; i++) {
        
                for(int j=0; j<n; j++) {
                
                        graph[i][j] = 0;
                }       
        }
        
        
        for(int i=0; i<r; i++) {                // preparing adjacency matrix from the given input
                ind = edg[i][0];
                ind_end = edg[i][1];
                val = edg[i][2];
                graph[ind][ind_end] = val;
                graph[ind_end][ind] = val;
        
        }
        
        Dij(n, graph, m);  // calling Djikstra algorithm with source m

        return 0;
}