у меня курсовая на данную тему.
ввод данных из файла (первая строка - количество вершин, далее как и обычная матрица) в матрицу весов. нужно найти и вывести кратчайший путь для любых двух вершин в графе если он существует. написал прогу, в которой попытался реализвовать оба эти алгоритма.
***
Алгоритм Флойда работает замечательно, всё получается... и новую матрицу вычисляет правильно и путь тоже находит верный.
может быть дадите совет как можно вывести все кратчайшие пути для данных двух вершин, т.к. и такое может быть...
***
с алгоритмом дейкстры есть небольшие сложности...
если я нахожу путь из 1 вершины во все остальные, то путь находит верный...
если путь ищу из какой-то другой вершины, то программу зацикливает... глаз замылен уже и может быть просто не вижу своей ошибки... а может быть данный алгоритм находит пути только для 1-й вершины, не знаю... поэтому тоже прошу совета...
***
мне надо сравнить время работы этих алгоритмов, как это можно сделать в СИ++ не знаю... очень прошу немного помочь мне разобраться в этом...
| Код |
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<values.h>
#include<stdlib.h>
int start, finish, z, min;
int **matrix, **a, **p; // matrix
int node; // Number of graph nodes
int *s, *b, *c;
//---------------------------------------------------------------------------
void f1() // enter matrix
{
int i, j;
FILE *in=0;
// in=fopen("123456.txt", "r");
in=fopen("ford2.txt", "r");
fscanf(in, "%d", &node);
puts("");
printf("Number of nodes: %d", node);
puts("");
matrix=(int **) malloc(node*sizeof(int)); // allocating memory for matrix
for (i=0; i<node; i++)
matrix[i]=(int *) malloc(node*sizeof(int));
for (i=0; i<node; i++) // reading matrix
for (j=0; j<node; j++)
{
fscanf(in, "%d", &matrix[i][j]);
if ( matrix[i][j]==0 ) matrix[i][j]=MAXINT;
}
for (i=0; i<node; i++)
matrix[i][i]=0;
puts("");
}
//---------------------------------------------------------------------------
void f2() // printing matrix
{
int i, j; /*
for (i=0; i<node; i++)
{
for (j=0; j<node; j++)
if (j==0) printf("%d", matrix[i][j]);
else printf("%3d", matrix[i][j]);
puts("");
} */
puts("");
for (i=0; i<node; i++)
{
j=0;
if (matrix[i][j]==MAXINT) printf("%4c ", '-');
else printf("%4d ", matrix[i][j]);
for (j=1; j<node; j++)
if (matrix[i][j]==MAXINT) printf("%4c ", '-');
else printf("%4d ", matrix[i][j]);
puts("");
}
puts("");
}
//---------------------------------------------------------------------------
void path(int i, int j)
{
if (p[i][j]!=i+1)
{
path(i, p[i][j]-1);
printf("%d, ", p[i][j]);
}
}
//---------------------------------------------------------------------------
void f3() // Floid Algoritm
{
int i, j, k;
a=(int **) malloc(node*sizeof(int));
for (i=0; i<node; i++)
a[i]=(int *) malloc(node*sizeof(int));
p=(int **) malloc(node*sizeof(int));
for (i=0; i<node; i++)
p[i]=(int *) malloc(node*sizeof(int));
for (i=0; i<node; i++)
for (j=0; j<node; j++)
{
a[i][j]=matrix[i][j];
p[i][j]=i+1;
}
for (k=0; k<node; k++)
for (i=0; i<node; i++)
for (j=0; j<node; j++)
{
long tmp;
tmp=(long)a[i][k]+a[k][j];
if (tmp<a[i][j])
{
a[i][j]=tmp;
p[i][j]=k+1;
}
}
for (i=0; i<node; i++)
{
for (j=0; j<node; j++)
if (a[i][j]==MAXINT) printf("%6c", '-');
else printf("%6d", a[i][j]);
puts("");
}
puts("");
for (i=0; i<node; i++)
{
for (j=0; j<node; j++)
printf("%6d", p[i][j]);
puts("");
}
printf("Enter start point: ");
scanf("%d", &start);
printf("Enter end point: ");
scanf("%d", &finish);
start--;
finish--;
if ( a[start][finish]==MAXINT ) printf("there is no path\n");
else if (finish==start) printf("start and end points are the same!\n");
else
{
printf("\nMinimum Path from %d to %d = %d\n", start+1, finish+1, a[start][finish]);
printf("%d, ", start+1);
path(start, finish);
printf("%d", finish+1);
puts("");
}
puts("");
}
//---------------------------------------------------------------------------
void path1()
{
printf("%d <- ", finish+1);
z=c[finish];
while (z!=0)
{
printf("%d <- ", z+1);
z=c[z];
}
printf("%d <- start", start+1);
puts("");
}
//---------------------------------------------------------------------------
int check()
{
int f=node;
for (int i=0; i<node; i++)
if (s[i]) f--;
return f;
}
//---------------------------------------------------------------------------
void f4() // Edsger Wybe Dijkstra Algoritm
{
int i, j, k;
s=(int *) malloc(node*sizeof(int));
c=(int *) malloc(node*sizeof(int));
b=(int *) malloc(node*sizeof(int));
for (i=0; i<node; i++)
s[i]=0;
printf("\nEnter start point: ");
scanf("%d", &start);
printf("Enter end point: ");
scanf("%d", &finish);
start--; finish--;
for (i=0; i<node; i++)
c[i]=start;
s[start]=1; c[start]=0;
for (i=0; i<node; i++)
b[i]=matrix[start][i];
while (check())
{
min=MAXINT;
for (i=0; i<node; i++)
if (s[i]==0)
if (b[i]<min)
{
min=b[i];
j=i;
}
s[j]=1;
for (k=0; k<node; k++)
if (s[k]==0)
{
long tmp;
tmp=(long)b[j]+matrix[j][k];
if (tmp<b[k])
{
b[k]=tmp;
c[k]=j;
}
}
}
/*
printf("%6d\n", min);
for (i=0; i<node; i++)
printf("%6d", s[i]);
puts("");
for (i=0; i<node; i++)
printf("%6d", b[i]);
puts("");
*/
for (i=0; i<node; i++)
printf("%6d", c[i]+1);
puts("");
if (b[finish]==MAXINT) printf("There is no path\n");
else
{
printf("Minimum path from %d to %d = %d\n", start+1, finish+1, b[finish]);
if (start==finish) printf("start and end points are the same!!!");
else if (c[finish]==0) printf("%d <- %d <- start", start+1, finish+1);
else path1();
}
puts("");
}
//---------------------------------------------------------------------------
int menu()
{
int a;
while (1){
printf("Menu:\n");
printf("1 - Input Matrix\n");
printf("2 - Output Matrix\n");
printf("3 - Floid Algoritm\n");
printf("4 - Dijkstra Algoritm\n");
printf("9 - Clear Screen\n");
printf("0 - Exit Program\n");
printf("Select: ");
scanf("%d", &a);
switch (a) {
case 0: return 0;
case 1: f1(); break;
case 2: f2(); break;
case 3: f3(); break;
case 4: f4(); break;
case 9: clrscr(); break;
default: printf("Wrong character!!!\n");
}
}
}
//---------------------------------------------------------------------------
main()
{
clrscr();
menu();
return 0;
}
|
вот пара текстовых файлов с которыми я работал
| Код |
13
0 2 4 6 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 7 0 0 0 0 0 0
0 0 0 2 0 0 6 0 0 0 0 0 0
0 0 0 0 5 3 0 0 0 0 0 0 0
0 0 0 0 0 0 0 9 0 3 0 0 0
0 0 0 0 2 0 5 0 0 0 0 0 0
0 0 0 0 0 0 0 10 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 5 0
0 0 0 0 0 0 0 2 0 0 9 0 0
0 0 0 0 0 0 0 0 2 0 10 0 0
0 0 0 0 0 0 0 0 0 0 0 0 4
0 0 0 0 0 0 0 0 0 0 2 0 8
0 0 0 0 0 0 0 0 0 0 0 0 0
|
| Код |
8
0 3 4 7 0 0 0 0
0 0 1 0 5 11 8 0
0 0 0 2 7 10 0 0
0 0 0 0 2 8 0 12
0 0 0 0 0 5 2 10
0 0 0 0 0 0 0 4
0 0 0 0 0 3 0 8
0 0 0 0 0 0 0 0
|
|
