Bellman-ford algorithm implementation in Java, and C

Bellman Ford algorithm is an algorithm of finding shortest path in a graph from the given source.

let us take an example of a graph:

Source Code in C:

#include <stdio.h>

#include <stdlib.h>

#include <strings.h>

#include <limits.h>

struct Edge

{

int src,dst,wt;

};

struct Graph

{

int V,E;

struct Edge *edge;

};

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];

    // Step 1: Initialize distances from src to all other vertices

    // as INFINITE

    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].dst;

            int weight = graph->edge[j].wt;

            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].dst;

        int weight = graph->edge[i].wt;

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

            printf("Graph contains negative weight cycle");

    }

    printArr(dist, V);

    return;

}

int main()

{

   printf(" this is the first program\n");

   int vertex =5;

   int edge =8;

   struct Graph *graph = (struct Graph *)malloc(sizeof(struct Graph));

   graph->V = vertex;

   graph->E = edge;

   graph->edge= (struct Edge*) malloc( graph->E * sizeof( struct Edge ) );

   //add the node for vertex A -B

   graph->edge[0].src = 0;

   graph->edge[0].dst = 1;

   graph->edge[0].wt = -1;

    //add the node for vertex A-C

   graph->edge[1].src = 0;

   graph->edge[1].dst = 2;

   graph->edge[1].wt = 4;

   

      //add the node for vertex B-C

   graph->edge[2].src = 1;

   graph->edge[2].dst = 2;

   graph->edge[2].wt = 3;

      //add the node for vertex B-D

   graph->edge[3].src = 1;

   graph->edge[3].dst = 4;

   graph->edge[3].wt = 2;

      //add the node for vertex  B-E

   graph->edge[4].src = 0;

   graph->edge[4].dst = 1;

   graph->edge[4].wt = -1;

      //add the node for vertex E-D

   graph->edge[5].src = 4;

   graph->edge[5].dst = 3;

   graph->edge[5].wt = -3;

      //add the node for vertex D-B

   graph->edge[6].src = 3;

   graph->edge[6].dst = 1;

   graph->edge[6].wt = 1;

      //add the node for vertex D-C

   graph->edge[7].src = 3;

   graph->edge[7].dst = 2;

   graph->edge[7].wt = 5;  

   BellmanFord(graph, 0);

    return 0;

}

Source Code in Java:

/** * Created by laxmikadariya on 2/15/17. */
import java.util.*;
import java.lang.*;
import java.io.*;


class Graph{

    int V,E;

    class Edge{
        int src, dst,wt;
        Edge(){
            src=dst=wt=0;
        }


    }
    Edge edge[];

    Graph(int v,int e)
    {
        V=v;
        E=e;
        edge = new Edge[e];
        for (int i=0;i<e;i++)
        {
            edge[i]=new Edge();
        }


    }

    void BellmanFord(Graph graph,int src)
    {
        int V = graph.V, E = graph.E;
        int dist[] = new int[V];

              for (int i=0; i<V; ++i)
            dist[i] = Integer.MAX_VALUE;
        dist[src] = 0;

         for (int i=1; i<V; ++i)
        {
            for (int j=0; j<E; ++j)
            {
                int u = graph.edge[j].src;
                int v = graph.edge[j].dst;
                int weight = graph.edge[j].wt;
                if (dist[u]!=Integer.MAX_VALUE &&
                        dist[u]+weight<dist[v])
                    dist[v]=dist[u]+weight;
            }
        }

       
        for (int j=0; j<E; ++j)
        {
            int u = graph.edge[j].src;
            int v = graph.edge[j].dst;
            int weight = graph.edge[j].wt;
            if (dist[u]!=Integer.MAX_VALUE &&
                    dist[u]+weight<dist[v])
                System.out.println("Graph contains negative weight cycle");
        }
        System.out.println("Vertex   Distance from Source");
        for (int i=0; i<V; ++i)
            System.out.println(i+"\t\t"+dist[i]);
    }


}
public class bellmon_ford {


    public static void main(String[] args) {
        int V = 5;
        int E = 8;
        Graph graph =  new Graph(V,E);



        //add the node for vertex A -B        

        graph.edge[0].src=0;
        graph.edge[0].dst = 1;
        graph.edge[0].wt = -1;


        //add the node for vertex A-C       

        graph.edge[1].src = 0;
        graph.edge[1].dst = 2;
        graph.edge[1].wt = 4;

        //add the node for vertex B-C        

        graph.edge[2].src = 1;
        graph.edge[2].dst = 2;
        graph.edge[2].wt = 3;

        //add the node for vertex B-D       

         graph.edge[3].src = 1;
        graph.edge[3].dst = 4;
        graph.edge[3].wt = 2;


        //add the node for vertex  B-E       

        graph.edge[4].src = 0;
        graph.edge[4].dst = 1;
        graph.edge[4].wt = -1;


        //add the node for vertex E-D        

        graph.edge[5].src = 4;
        graph.edge[5].dst = 3;
        graph.edge[5].wt = -3;


        //add the node for vertex D-B        

        graph.edge[6].src = 3;
        graph.edge[6].dst = 1;
        graph.edge[6].wt = 1;


        //add the node for vertex D-C        

        graph.edge[7].src = 3;
        graph.edge[7].dst = 2;
        graph.edge[7].wt = 5;

        graph.BellmanFord(graph, 0);



    }
}

Reversing each word of the string with blank space preserved in Python and Java

we can come in the situation that we need to reverse each word of the string and also we need to preserve the blank space i.e we may have more than one space character in between each word and that needs to be preserved as well. Here I have mentioned the code for Python and Java.

Input:   "   I         am Laxmi     Kadariya"

Output:     I         ma imxaL     ayiradaK 

Algorithm:

1) split the string in to words:

2) reverse each word

3) finally join all the reverse word with space

def rev_string(test):
 final_str = ''
 words = test.split(' ')
 for x in words:
  rev_word = x[::-1]
  final_str = final_str + rev_word + ' ' 

 print final_str


 
  



if __name__ == '__main__':
 test = "   I         am Laxmi     Kadariya"
 rev_string(test)

Java Code:

/**
 * Created by laxmikadariya on 2/8/17.
 */
public class string_rev {
    static void reverseEachWordOfString(String inputString)
    {
        String[] words = inputString.split(" ");

        String reverseString = "";

        for (int i = 0; i < words.length; i++)
        {
            String word = words[i];


            String reverseWord = "";

            for (int j = word.length()-1; j >= 0; j--)
            {
                reverseWord = reverseWord + word.charAt(j);
            }

            reverseString = reverseString + reverseWord + " ";
        }

        System.out.println(inputString);

        System.out.println(reverseString);

        System.out.println("-------------------------");
    }

    public static void main(String[] args)
    {
        reverseEachWordOfString("   I am     Laxmi Kadariya");

    }
}