Code:
#include <stdio.h>
#include <limits.h>
#include <assert.h>
typedef enum {false, true} bool; /* The order is rather important to
get the boolean values right. */
typedef char *string;
/*
We define a type of values for weights, which can be changed (to
e.g. floats) if required.But the algorithm works for nonnegative values only.
*/
#define oo UINT_MAX /* infinity is represented as the maximum unsigned int. */
typedef unsigned int value;
/*
In order to avoid complications with IO, we include the graph in
the program directly. Of course, one wouldn't do that in practice.
*/
/* The (non)vertex `nonexistent' is used in order to indicate that a vertex hasn't got a predecessor
in the path under consideration. */
typedef enum{ ArtsTheatre,NewArtsBlock,OpenAirTheatre,GeographyDept,FacultyOfAgriculture,PGIA,MeewathuraFarm ,FacultyOfDentalScience,FacultyOfEngineering,FacultyOfMedicine,TeachingHospital,FacultyOfScience,GeologyDepartment,VetFaculty,SwineProductionUnit,UniversityFarm,ExternalExaminationBranch,FacultyClub,HallMaintenaceDept,LandscapeBranch,MaintenanceServiceDept,SecurityOffice,SenateBuilding ,StudentCentre,TelephoneExchange,Library,USO,HealthCentre,SportsArena,Gymnasium,StaffRecreationClub,SwimmingPool,AkbarHall,ArunachalamHall,HildaObeysekaraHall,JamesPeirisHall,JayathilakaHall,MarcusFernandoHall,MarrsHall,RamanathanHall,SangamittaHall,WijewardanaHall,HindagalaHall,BhikkuHostel,KehelpannalaBhikkuHostel,Sangaramaya,GuestHouse,Stupa,ChristChurch,VCResidence ,ITCentre,Mosque,HinduKowil,Lodge,nonexistent}vertex;
const vertex first_vertex = ArtsTheatre;
const vertex last_vertex = Lodge;
#define no_vertices 54 /* This has to be the same as the number
(last_vertex + 1), but being using it,it
doesn't compile... */
/*This part is for getting clear output */
string name[] = {"ArtsTheatre","NewArtsBlock","OpenAirTheatre","GeographyDept","FacultyOfAgriculture","PGIA","MeewathuraFarm ","FacultyOfDentalScience","FacultyOfEngineering","FacultyOfMedicine","TeachingHospital","FacultyOfScience","GeologyDepartment","VetFaculty","SwineProductionUnit","UniversityFarm","ExternalExaminationBranch","FacultyClub","HallMaintenaceDept","LandscapeBranch","MaintenanceServiceDept","SecurityOffice","SenateBuilding" ,"StudentCentre","TelephoneExchange","Library","USO","HealthCentre","SportsArena","Gymnasium","StaffRecreationClub","SwimmingPool","AkbarHall","ArunachalamHall","HildaObeysekaraHall","JamesPeirisHall","JayathilakaHall","MarcusFernandoHall","MarrsHall","RamanathanHall","SangamittaHall","WijewardanaHall","HindagalaHall","BhikkuHostel","KehelpannalaBhikkuHostel","Sangaramaya","GuestHouse","Stupa","ChristChurch","VCResidence","ITCentre","Mosque","HinduKowil","Lodge"};
value weight[no_vertices][no_vertices] =
{
{0,46,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,188,oo,oo,189,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{46,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,188,oo,oo,oo,349,oo,oo,oo,oo,328,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,275,oo,oo,oo,oo,oo,oo}, {oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,332,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,101,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,157,oo,oo,oo,oo,oo,0},
{oo,oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,72,oo,134,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,474,oo,oo,410,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,362,353,oo,oo,514,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,977,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,0,oo,oo,oo,oo,oo,527,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,88,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,134,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,193,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,354,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,0,436,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,191,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,299,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,436,0,oo,oo,oo,oo,oo,263,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,240,oo,oo,239,oo,oo,122,oo,oo,oo,oo,124,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,527,oo,oo,oo,oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,93,oo,111,oo,oo,oo,151,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,0,316,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,316,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,205,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,362,oo,oo,oo,oo,263,oo,oo,oo,oo,oo,0,82,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,474,353,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,82,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,269,oo,oo,oo,oo,oo,oo,oo,oo,oo,176,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,374,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,0,oo,oo,oo,oo,11,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,52,oo},
{oo,oo,oo,oo,410,514,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,121,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,0,oo,oo,164,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{188,oo,332,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,0,oo,oo,71,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,234,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,72,oo,oo,oo,oo,oo,oo,oo,oo,93,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,188,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,11,oo,164,oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,62,oo},
{189,oo,oo,134,oo,oo,oo,oo,oo,oo,oo,oo,111,oo,oo,oo,oo,oo,oo,oo,oo,oo,71,oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,134,oo,191,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,172,oo,oo,446,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,269,oo,oo,oo,oo,oo,oo,oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,162,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,242,oo,oo},
{oo,349,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,151,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,0,oo,81,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,240,oo,oo,oo,oo,oo,oo,oo,oo,121,oo,oo,oo,oo,oo,oo,oo,oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,88,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,88,oo,193,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,328,oo,oo,oo,oo,oo,oo,oo,oo,oo,239,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,0,oo,oo,188,oo,oo,oo,oo,oo,oo,133,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,101,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,0,oo,oo,oo,oo,oo,218,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,0,oo,149,oo,oo,oo,oo,oo,oo,oo,oo,oo,216,oo,oo,oo,oo,oo,98},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,122,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,188,oo,oo,0,oo,410,oo,oo,139,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,176,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,149,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,614,877,oo,oo,288,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,172,oo,oo,oo,oo,oo,oo,oo,oo,oo,410,oo,0,oo,oo,330,oo,oo,oo,oo,oo,oo,oo,622,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,0,254.54,oo,484,oo,255,oo,oo,oo,oo,oo,oo,187,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,162,oo,oo,oo,oo,oo,oo,218,oo,oo,oo,oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,299,oo,124,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,446,oo,oo,oo,oo,oo,oo,oo,oo,oo,139,oo,330,oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,484,oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,393,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,133,oo,oo,oo,oo,oo,oo,oo,oo,oo,0,oo,oo,78,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,255,oo,oo,oo,oo,0,144,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,977,oo,oo,354,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,144,0,oo,oo,oo,oo,oo,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,78,oo,oo,0,oo,oo,oo,260,oo,oo,oo},
{oo,oo,157,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,234,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,216,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,0,oo,oo,oo,oo,oo,oo},
{oo,275,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,205,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,614,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,0,oo,370,oo,517,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,877,622,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,0,389,oo,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,260,oo,370,389,0,oo,241,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,374,oo,oo,oo,oo,oo,oo,oo,oo,242,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,187,oo,oo,393,oo,oo,oo,oo,oo,oo,oo,oo,0,oo,oo},
{oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,52,oo,oo,oo,oo,62,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,288,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,517,oo,241,oo,0,oo},
{oo,oo,0,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,98,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,oo,0}
};
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* The implementation of Dijkstra's algorithm starts here. *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
value D[no_vertices];
bool tight[no_vertices];
vertex predecessor[no_vertices];
vertex minimal_nontight() {
vertex j, u;
for (j = first_vertex; j <= last_vertex; j++)
if (!tight[j])
break;
assert(j <= last_vertex);
u = j;
for (j++; j <= last_vertex; j++)
if (!tight[j] && D[j] < D[u])
u = j;
/* Having checked all vertices, we now know that u has the required
minimality property. */
return u;
}
bool successor(vertex u, vertex z) {
return (weight[u][z] != oo && u != z);
}
void dijkstra(vertex s) {
vertex z, u;
int i;
D[s] = 0;
for (z = first_vertex; z <= last_vertex; z++) {
if (z != s)
D[z] = oo;
tight[z] = false;
predecessor[z] = nonexistent;
}
for (i = 0; i < no_vertices; i++) {
u = minimal_nontight();
tight[u] = true;
/* In a disconnected graph, D[u] can be oo. But then we just move
on to the next iteration of the loop. */
if (D[u] == oo)
continue; /* to next iteration ofthe for loop */
for (z = first_vertex; z <= last_vertex; z++)
if (successor(u,z) && !tight[z] && D[u] + weight[u][z] < D[z]) {
D[z] = D[u] + weight[u][z]; /* Shortcut found. */
predecessor[z] = u;
}
}
}
#define stack_limit 1000000 /* Arbitrary choice. Has to be big enough to
accomodate the largest path. */
vertex stack[stack_limit];
unsigned int sp = 0; /* Stack pointer. */
void push(vertex u) {
assert(sp < stack_limit); /* We abort if the limit is exceeded. This
will happen if a path with more
vertices than stack_limit is found. */
stack[sp] = u;
sp++;
}
bool stack_empty() {
return (sp == 0);
}
vertex pop() {
assert(!stack_empty()); /* We abort if the stack is empty. This will
happen if this program has a bug. */
sp--;
return stack[sp];
}
/* End of stack digression and back to printing paths. */
void print_shortest_path(vertex origin, vertex destination) {
vertex v;
assert(origin != nonexistent && destination != nonexistent);
dijkstra(origin);
printf("The shortest path from %s to %s is:\n\n",
name[origin], name[destination]);
for (v = destination; v != origin; v = predecessor[v])
if (v == nonexistent) {
printf("nonexistent (because the graph is disconnected).\n");
return;
}
else
push(v);
push(origin);
while (!stack_empty())
printf(" %s",name[pop()]);
printf(".\n\n");
}
/* We now run an example. */
int main() {
FILE *infile;
value weight[no_vertices][no_vertices];
value row,col;
infile = fopen ("mapdata.txt","r");
for (row=0; row < no_vertices; row +=1)
{
for (col=0; col < no_vertices; col +=1)
{
fscanf(infile,"%d",&weight[row][col]);
}
fclose(infile);
}
print_shortest_path(ArtsTheatre,Lodge);
return 0; /* Return gracefully to the caller of the program
(provided the assertions above haven't failed). */
}