C C++ Java Data Structure Python JavaScript CSS Ajax PL/SQL PHP Puzzles C programs C++ programs Java programs

Home » Data Structure

In this example, we will learn about weighted graph with positive and negative weights, shortest path and Warshall’s algorithm. Submitted by Manu Jemini, on January 09, 2018

Image source: http://mathworld.wolfram.com/images/eps-gif/GraphNodesEdges_1000.gif

A weighted graph with positive and negative weights can be understood as a graph with edges having cost. Edge is the line connecting two nodes or a pair of nodes. The cost can be positive or negative.

Image source: https://i.stack.imgur.com/GlrNb.png

The shortest distance is the distance between two nodes. For Example, to reach a city from another, can have multiple paths with the different number of costs. A path with the minimum possible cost is the shortest distance.

Image source: https://i.stack.imgur.com/tyTz7.png

Warshall’s algorithm is an algorithm which is used to find the shortest path between the source and destination nodes. These types of problems generally solved with BST if the cost of every edge is 1. But here the edges can have different values, even negative values. Hence we need to use this algorithm.

C program

#include <stdio.h> #define infinity 9999 #define MAX 20 int minimum(int a,int b) { if(a<=b) return a; else return b; }/*End of minimum()*/ int display(int matrix[MAX][MAX],int n ) { int i,j; for(i=0;i<n;i++) { for(j=0;j<n;j++) printf("%7d",matrix[i][j]); printf("\n"); } }/*End of display()*/ main() { int i,j,k,n; int adj[MAX][MAX],path[MAX][MAX]; printf("Enter number of vertices : "); scanf("%d",&n); printf("Enter weighted matrix :\n"); for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d",&adj[i][j]); printf("Weighted matrix is :\n"); display(adj,n); /*Replace all zero entries of adjacency matrix with infinity*/ for(i=0;i<n;i++) for(j=0;j<n;j++) if(adj[i][j]==0) path[i][j]=infinity; else path[i][j]=adj[i][j]; for(k=0;k<n;k++) { printf("Q%d is :\n",k); display(path,n); for(i=0;i<n;i++) for(j=0;j<n;j++) path[i][j]=minimum( path[i][j] , path[i][k]+path[k][j] ); } printf("Shortest path matrix Q%d is :\n",k); display(path,n); }/*End of main() */

Output

Advertisements

Liked this article? Do share with your friends :)

C, C++, Java, D.S., Python, .Net, SQL, PL/SQL, Ajax, PHP, JavaScript, CSS, HTML, C programs, C++ programs, Java programs, C# programs, DS programs, C aptitude, C++ aptitude, Java aptitude, DBMS aptitude, O.S., Networking, Embedded systems, Nanotechnologies, Linux, DOS, puzzles, syntaxes,

~ RECENT POSTS ~

Find the factorial of any number with the use of tail recursion

Installation of Android Studio

Sending data on server through an Android Application

Android Application Connectivity with the Server

Explain Structures with Example in C#