Showing posts with label Dijkstra implementation using Java. Show all posts
Showing posts with label Dijkstra implementation using Java. Show all posts

Thursday, 3 January 2013

Dijkstra algorithm's implementation in java (From one source to all the other nodes in Graph)


import java.io.*;
class Tnode
{
int prev;
int len;
char label;
boolean vis;
public Tnode(char lab)
 {
   label = lab;
   prev=-1;
   len=100000;
   vis=false;
 }
}

Friday, 21 December 2012

Dijkstra algorithm's implementation in java (From one source to one destination in Graph)


import java.io.*;
class Tnode
{
int prev;
int len;
char label;
boolean vis;
public Tnode(char lab)
 {
   label = lab;
   prev=-1;
   len=100000;
   vis=false;
 }
}
class graph
{
  public final int MAX = 20;
  public int nverts,i,min;
  public Tnode vlist[];
  public int adj[][];
  public graph()
  {
   nverts = 0;
   adj = new int[MAX][MAX];
   vlist = new Tnode[MAX];
   for(int i=0;i<MAX;i++)
 {
for(int j=0;j<MAX;j++)
adj[i][j] = 0;
 }
  }
  public void addver(char lab)
  {
    vlist[nverts++] = new Tnode(lab);
  }
  public void addedge(int start,int end,int cost)
  {
    adj[start][end] = cost;
  }
  public int getind(char l)
  {
    for(int i=0;i<nverts;i++)
      if(vlist[i].label==l)
      return i;
    return (MAX+1);
  }
  public void brfs(int src, int dest)
  {
 int k;
 int path[]=new int[20];
 vlist[src].len=0;
 vlist[src].vis=true;
k=src;
do{
for(i=0;i<nverts;i++)
{
if((adj[k][i]!=0)&&(vlist[i].vis==false))
{
if(vlist[k].len+adj[k][i]<vlist[i].len)
{
vlist[i].prev=k;
vlist[i].len=vlist[k].len+adj[k][i];
}
}
}
k=0;
min=100000;
for(i=0;i<nverts;i++)
{
if((vlist[i].vis==false)&&(vlist[i].len<min))
{
min=vlist[i].len;
k=i;
}
}
vlist[k].vis=true;
 }while(k!=dest);
i=0;
k=dest;
int c=0;
do{
path[i++]=k;
c++;
k=vlist[k].prev;
}while(k>=0);
System.out.println("shortest path from source to destination is \n");
for(i=c-1;i>=0;i--)
System.out.print("-->"+vlist[path[i]].label);
System.out.println("\n shortest distance from source to destination is \n"+vlist[dest].len);
}
}

Best geography books for UPSC prelims, mains

This post is intended to clear the confusion that prevails among the aspirants over how to prepare for UPSC geography and the best books f...