Question

Problem #1 Let a "path" on a weighted graph G = (V,E,W) be defined as a sequence of distinct vertices V-(vi,v2, ,%)-V connected by a sequence of edges {(vi, t), (Ug, ta), , (4-1,Un)) : We say that (V, E) is a path from tovn. Sketch a graph with 10 vertices and a path consisting of 5 vertices and four edges. Formulate a binary integer program that could be used to find the path of least total weight from one given vertex, say v, to another given vertex, say vs.

Answer 1

For the above problem, we can use Dijkstras shortestpath algorithm:

The below program will ask the user for number of vertices in th graph

After giving the vertex count

User will be prompted for weighted matrix (Edge weights from one vertex to another vertex)

User will be promted for source vertex (from which the distance to be calculated)

User will be prompted for destination vertex (to which the shortest distance to be calculated)

............................................................................................................................................................................

import java.util.HashSet;

import java.util.InputMismatchException;

import java.util.Iterator;

import java.util.Scanner;

import java.util.Set;

public class Dijkstras_Shortest_Path

{

    private int distances[];

    private Set<Integer> settled;

    private Set<Integer> unsettled;

    private int number_of_nodes;

    private int adjacencyMatrix[][];

    public Dijkstras_Shortest_Path(int number_of_nodes)

    {

        this.number_of_nodes = number_of_nodes;

        distances = new int[number_of_nodes + 1];

        settled = new HashSet<Integer>();

        unsettled = new HashSet<Integer>();

        adjacencyMatrix = new int[number_of_nodes + 1][number_of_nodes + 1];

    }

    public void dijkstra_algorithm(int adjacency_matrix[][], int source)

    {

        int evaluationNode;

        for (int i = 1; i <= number_of_nodes; i++)

            for (int j = 1; j <= number_of_nodes; j++)

                adjacencyMatrix[i][j] = adjacency_matrix[i][j];

        for (int i = 1; i <= number_of_nodes; i++)

        {

            distances[i] = Integer.MAX_VALUE;

        }

        unsettled.add(source);

        distances[source] = 0;

        while (!unsettled.isEmpty())

        {

            evaluationNode = getNodeWithMinimumDistanceFromUnsettled();

            unsettled.remove(evaluationNode);

            settled.add(evaluationNode);

            evaluateNeighbours(evaluationNode);

        }

    }

    private int getNodeWithMinimumDistanceFromUnsettled()

    {

        int min;

        int node = 0;

        Iterator<Integer> iterator = unsettled.iterator();

        node = iterator.next();

        min = distances[node];

        for (int i = 1; i <= distances.length; i++)

        {

            if (unsettled.contains(i))

            {

                if (distances[i] <= min)

                {

                    min = distances[i];

                    node = i;

                }

            }

        }

        return node;

    }

    private void evaluateNeighbours(int evaluationNode)

    {

        int edgeDistance = -1;

        int newDistance = -1;

        for (int destinationNode = 1; destinationNode <= number_of_nodes; destinationNode++)

        {

            if (!settled.contains(destinationNode))

            {

                if (adjacencyMatrix[evaluationNode][destinationNode] != Integer.MAX_VALUE)

                {

                    edgeDistance = adjacencyMatrix[evaluationNode][destinationNode];

                    newDistance = distances[evaluationNode] + edgeDistance;

                    if (newDistance < distances[destinationNode])

                    {

                        distances[destinationNode] = newDistance;

                    }

                    unsettled.add(destinationNode);

                }

            }

        }

    }

    public static void main(String... arg)

    {

        int adjacency_matrix[][];

        int number_of_vertices;

        int source = 0, destination = 0;

        Scanner scan = new Scanner(System.in);

        try

        {

            System.out.println("Enter the number of vertices");

            number_of_vertices = scan.nextInt();

            adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];

            System.out.println("Enter the Weighted Matrix for the graph");

            for (int i = 1; i <= number_of_vertices; i++)

            {

                for (int j = 1; j <= number_of_vertices; j++)

                {

                    adjacency_matrix[i][j] = scan.nextInt();

                    if (i == j)

                    {

                        adjacency_matrix[i][j] = 0;

                        continue;

                    }

                    if (adjacency_matrix[i][j] == 0)

                    {

                        adjacency_matrix[i][j] = Integer.MAX_VALUE;

                    }

                }

            }

            System.out.println("Enter the source(u): ");

            source = scan.nextInt();

            System.out.println("Enter the destination (v): ");

            destination = scan.nextInt();

            Dijkstras_Shortest_Path dijkstrasAlgorithm = new Dijkstras_Shortest_Path(

                    number_of_vertices);

            dijkstrasAlgorithm.dijkstra_algorithm(adjacency_matrix, source);

            System.out.println("The Shorted Path from " + source + " to " + destination + " is: ");

            for (int i = 1; i <= dijkstrasAlgorithm.distances.length - 1; i++)

            {

                if (i == destination)

                    System.out.println(source + " to " + i + " is "

                            + dijkstrasAlgorithm.distances[i]);

            }

        } catch (InputMismatchException inputMismatch)

        {

            System.out.println("Wrong Input Format");

        }

        scan.close();

    }

}