Travelling Salesman Problem

The travelling salesman problem is a graph computational problem where

the salesman needs to visit all cities (represented using nodes in a graph)
in a list just once and the distances (represented using edges in the graph)
between all these cities are known. The solution that is needed to be found
for this problem is the shortest possible route in which the salesman visits
all the cities and returns to the origin city.

If you look at the graph below, considering that the salesman starts from
the vertex ‘a’, they need to travel through all the remaining vertices b, c,
d, e, f and get back to ‘a’ while making sure that the cost taken is
minimum.

There are various approaches to find the solution to the travelling

salesman problem: naive approach, greedy approach, dynamic
programming approach, etc.

Travelling Salesperson Algorithm

To find the best optimal solution locally to figure out the global optimal
solution. The inputs taken by the algorithm are the graph G {V, E}, where
V is the set of vertices and E is the set of edges. The shortest path of graph
G starting from one vertex returning to the same vertex is obtained as the
output.

Algorithm

• Travelling salesman problem takes a graph G {V, E} as an input and

declare another graph as the output (say G’) which will record the
path the salesman is going to take from one node to another.

• The algorithm begins by sorting all the edges in the input graph G
from the least distance to the largest distance.

• The first edge selected is the edge with least distance, and one of the
two vertices (say A and B) being the origin node (say A).

• Then among the adjacent edges of the node other than the origin
node (B), find the least cost edge and add it onto the output graph.

• Continue the process with further nodes making sure there are no
cycles in the output graph and the path reaches back to the origin
node A.

• However, if the origin is mentioned in the given problem, then the

solution must always start from that node only. Let us look at some
example problems to understand this better.

Examples

Consider the following graph with six cities and the distances between
them −
From the given graph, since the origin is already mentioned, the solution
must always start from that node. Among the edges leading from A, A →
B has the shortest distance.

Then, B → C has the shortest and only edge between; therefore, it is

included in the output graph.
There is only one edge between C → D, therefore it is added to the output
graph.

There are two outward edges from D. Even though, D → B has lower
distance than D → E, B is already visited once and it would form a cycle if
added to the output graph. Therefore, D → E is added into the output
graph.

There is only one edge from e, that is E → F. Therefore, it is added into the
output graph.
Again, even though F → C has lower distance than F → A, F → A is added
into the output graph to avoid the cycle that would form and C is already
visited once.

The shortest path that originates and ends at A is A → B → C → D → E →

F→A

The cost of the path is: 16 + 21 + 12 + 15 + 16 + 34 = 114.

Even though, the cost of path could be decreased if it originates from other
nodes but the question is not raised with respect to that.

Example

The complete implementation of Travelling Salesman Problem using

Greedy Approach is given below −

Program

#include <stdio.h>

int tsp_g[10][10] = {

{12, 30, 33, 10, 45},

{56, 22, 9, 15, 18},

{29, 13, 8, 5, 12},

{33, 28, 16, 10, 3},

{1, 4, 30, 24, 20}

};

int visited[10], n, cost = 0;

/* creating a function to generate the shortest path */

void travellingsalesman(int c){

int k, adj_vertex = 999;

int min = 999;

/* marking the vertices visited in an assigned array */

visited[c] = 1;
/* displaying the shortest path */

printf("%d ", c + 1);

/* checking the minimum cost edge in the graph */

for(k = 0; k < n; k++) {

if((tsp_g[c][k] != 0) && (visited[k] == 0)) {

if(tsp_g[c][k] < min) {

min = tsp_g[c][k];

adj_vertex = k;

if(min != 999) {

cost = cost + min;

if(adj_vertex == 999) {

adj_vertex = 0;

printf("%d", adj_vertex + 1);

cost = cost + tsp_g[c][adj_vertex];

return;

travellingsalesman(adj_vertex);
}

/* main function */

int main(){

int i, j;

n = 5;

for(i = 0; i < n; i++) {

visited[i] = 0;

printf("Shortest Path: ");

travellingsalesman(0);

printf("\nMinimum Cost: ");

printf("%d\n", cost);

return 0;

Output

Shortest Path: 1 4 5 2 3 1

Minimum Cost: 55
EVALUATION OF EXPRESSION

An expression is any word or group of words or symbols that generates a value

on evaluation. Parsing expression means analyzing the expression for its words
or symbols depending on a particular criterion. Expression parsing is a term
used in a programming language to evaluate arithmetic and logical expressions.

The way to write arithmetic expression is known as a notation. An arithmetic

expression can be written in three different but equivalent notations, i.e., without
changing the essence or output of an expression. These notations are −

• Infix Notation

• Prefix (Polish) Notation

• Postfix (Reverse-Polish) Notation

These notations are named as how they use operator in expression. We shall
learn the same here in this chapter.

Infix Notation

We write expression in infix notation, e.g. a - b + c, where operators are used in-
between operands. It is easy for us humans to read, write, and speak in infix
notation but the same does not go well with computing devices. An algorithm to
process infix notation could be difficult and costly in terms of time and space
consumption.

Prefix Notation

In this notation, operator is prefixed to operands, i.e. operator is written ahead

of operands. For example, +ab. This is equivalent to its infix notation a + b. Prefix
notation is also known as Polish Notation.

Postfix Notation
This notation style is known as Reversed Polish Notation. In this notation style,
the operator is postfixed to the operands i.e., the operator is written after the
operands. For example, ab+. This is equivalent to its infix notation a + b.

The following table briefly tries to show the difference in all three notations −

Sr.No. Infix Notation Prefix Notation Postfix Notation

1 a+b +ab ab+

2 (a + b) ∗ c ∗+abc ab+c∗

3 a ∗ (b + c) ∗a+bc abc+∗

4 a/b+c/d +/ab/cd ab/cd/+

5 (a + b) ∗ (c + d) ∗+ab+cd ab+cd+∗

6 ((a + b) ∗ c) - d -∗+abcd ab+c∗d-

Parsing Expressions

As we have discussed, it is not a very efficient way to design an algorithm or

program to parse infix notations. Instead, these infix notations are first converted
into either postfix or prefix notations and then computed.

To parse any arithmetic expression, we need to take care of operator precedence

and associativity also.

Precedence

When an operand is in between two different operators, which operator will take
the operand first, is decided by the precedence of an operator over others. For
example −
As multiplication operation has precedence over addition, b * c will be evaluated
first. A table of operator precedence is provided later.

Associativity

Associativity describes the rule where operators with the same precedence
appear in an expression. For example, in expression a + b − c, both + and − have
the same precedence, then which part of the expression will be evaluated first,
is determined by associativity of those operators. Here, both + and − are left
associative, so the expression will be evaluated as (a + b) − c.

Precedence and associativity determines the order of evaluation of an expression.

Following is an operator precedence and associativity table (highest to lowest) −

Sr.No. Operator Precedence Associativity

Right
1 Exponentiation ^ Highest
Associative

Multiplication ( ∗ ) & Division ( Second

2 Left Associative
/) Highest

Addition ( + ) & Subtraction ( −

3 Lowest Left Associative
)

The above table shows the default behavior of operators. At any point of time in
expression evaluation, the order can be altered by using parenthesis. For
example −

In a + b*c, the expression part b*c will be evaluated first, with multiplication as
precedence over addition. We here use parenthesis for a + b to be evaluated first,
like (a + b)*c.
Postfix Evaluation Algorithm

We shall now look at the algorithm on how to evaluate postfix notation −

Step 1. Scan the expression from left to right

Step 2. If it is an operand push it to stack

Step 3. If it is an operator pull operand from stack and

perform operation

Step 4. Store the output of step 3, back to stack

Step 5. Scan the expression until all operands are consumed

Step 6. Pop the stack and perform operation

Expression Parsing - Complete implementation

Following are the complete implementations of Expression Parsing (Conversion

from infix notations to postfix notations) in various programming languages −

Example

#include<stdio.h>

#include<string.h>

#include<ctype.h>

//char stack

char stack[25];

int top = -1;

void push(char item) {

stack[++top] = item;

char pop() {
return stack[top--];

//returns precedence of operators

int precedence(char symbol) {

switch(symbol) {

case '+':

case '-':

return 2;

break;

case '*':

case '/':

return 3;

break;

case '^':

return 4;

break;

case '(':

case ')':

case '#':

return 1;

break;

}
}

//check whether the symbol is operator?

int isOperator(char symbol) {

switch(symbol) {

case '+':

case '-':

case '*':

case '/':

case '^':

case '(':

case ')':

return 1;

break;

default:

return 0;

//converts infix expression to postfix

void convert(char infix[],char postfix[]) {

int i,symbol,j = 0;
stack[++top] = '#';

for(i = 0;i<strlen(infix);i++) {

symbol = infix[i];

if(isOperator(symbol) == 0) {

postfix[j] = symbol;

j++;

} else {

if(symbol == '(') {

push(symbol);

} else {

if(symbol == ')') {

while(stack[top] != '(') {

postfix[j] = pop();

j++;

pop(); //pop out (.

} else {

if(precedence(symbol)>precedence(stack[top])) {
push(symbol);

} else {

while(precedence(symbol)<=precedence(stack[top])) {

postfix[j] = pop();

j++;

push(symbol);

while(stack[top] != '#') {

postfix[j] = pop();

j++;

postfix[j]='\0'; //null terminate string.

//int stack

int stack_int[25];
int top_int = -1;

void push_int(int item) {

stack_int[++top_int] = item;

char pop_int() {

return stack_int[top_int--];

//evaluates postfix expression

int evaluate(char *postfix){

char ch;

int i = 0,operand1,operand2;

while( (ch = postfix[i++]) != '\0') {

if(isdigit(ch)) {

push_int(ch-'0'); // Push the operand

} else {

//Operator,pop two operands

operand2 = pop_int();

operand1 = pop_int();

switch(ch) {

case '+':
push_int(operand1+operand2);

break;

case '-':

push_int(operand1-operand2);

break;

case '*':

push_int(operand1*operand2);

break;

case '/':

push_int(operand1/operand2);

break;

return stack_int[top_int];

void main() {

char infix[25] = "1*(2+3)",postfix[25];

convert(infix,postfix);

printf("Infix expression is: %s\n" , infix);

printf("Postfix expression is: %s\n" , postfix);

printf("Evaluated expression is: %d\n" , evaluate(postfix));

Output

Infix expression is: 1*(2+3)

Postfix expression is: 123+*

Evaluated expression is: 5

Expression Parsing Using Stack

We can use different data structures to implement expression parsing. Check

the implementation of Expression Parsing using Stack