Shortest Path using Dijkstra's Algorithm


1. Introduction:

Describe the problem: for the undirected graph G = (V, E) determine the shortest path from vertex to vertex C D of the graph G.
The idea of the algorithm: using Dijkstra's algorithm.
Description of inputs and outputs of the problem:
Input Data and graphs were connected to the file Bai6.inp.
- The first line contains the number n is the number of vertices in a graph (0 <n <100)
- The second line D peak and peak flow C.
- Line i + 2 (1 <= i <= n) contains n number of A [i, 1], A [i, 2], ..., A [i, n] each number separated by a space.
Data output: the output screen shortest path from D to C and peak values to find the shortest path.

dijkstra_exam

2. Source code:

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <values.h>
#define max 100
#define FileIn "Bai6.inp"
void Read_File(int A[max][max], int &n, int &D, int &C) {
FILE*f = fopen(FileIn,"rb");
fscanf(f,"%d%d%d",&n,&D,&C);
cout<<"Matrix corresponding link: \n";
cout<<D<<" "<<C<<endl;
for(int i =0;i<n;i++) {
for(int j =0;j<n;j++) {
fscanf(f,"%d",&A[i][j]);
cout<<A[i][j]<<" ";
}
cout<<endl;
}
fclose(f);
D--; C--;
}
void Dijkstra(int A[max][max], int n, int D, int C) {
char _Mark[max];
int _label[max], _before[max], XP, min;
for(int i=0; i<n; i++){
_label[i] = MAXINT;
_Mark[i] = 0;
_before[i] = D;
}
_label[D] = 0;
_Mark[D] = 1;
XP = D;
while(XP != C){
for(int j=0; j<n; j++)
if(A[XP][j]>0 && _label[j]>A[XP][j]+_label[XP] && _Mark[j]==0) {
_label[j] = A[XP][j]+_label[XP];
_before[j] = XP;
}
min = MAXINT;
for(j = 0; j<n; j++)
if(min>_label[j]&& _Mark[j]==0){
min = _label[j];
XP = j;
}
_Mark[XP] = 1;
}
cout<<"The shortest path:"<<_label[C]<<endl;
cout<<C+1<<" <-"<<_before[C]+1;
i = _before[C];
while(i!=D){
i = _before[i];
cout<<" <-"<<i+1;
}
}
void main() {
int A[max][max],n,_begin,_end;
Read_File(A,n,_begin,_end);
Dijkstra(A,n,_begin,_end);
getch();
}

3. Result:

Djistra_result_1


Advertisements