Anonymní profil Michal – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

Anonymní profil Michal – Programujte.comAnonymní profil Michal – Programujte.com

 

Příspěvky odeslané z IP adresy 93.99.96.–

Michal
C / C++ › Dijkstrův algoritmus
15. 12. 2016   #214071

Dobrý den,

Našel by se někdo, kdo by mě pomohl s tímto programem ? (zadání je na začátku v poznámce). Pátral na netu a nějak to spichl. Pro mě, jako začátečníka, je to docela těžké zadání a topím se v tom :( Sprovoznil jsem menu, načítání souboru s maticí a jednoduchý zápis do souboru TXT (nevím jak zapsat výsledek jako pořadí uzlů, takže zapisuju jen nejkratší cestu).

Podle mě, to nepočítá správně, ale jsem rád, že jsem to aspon nějak rozchodil :D

Neměl by někdo čas to vyzkoušet ? (txt musí být ve stejné složce jako program a program mám uložený jako .cpp).  A jestli to pracuje správně, což si teda nemyslím, jak to zapíšu tak, aby zapsal i to pořadí uzlů ? 

Předem děkuji za ochotu.

Pro začátek jsem začal jen s malou maticí.

6
0 2 3 0 0 0
2 0 4 5 0 0 
3 4 0 1 2 6 
0 5 1 0 2 1
0 0 2 2 0 3
0 0 0 1 3 0
/*
zpracujte projekt pro vyhledání nejkratší cesty v grafu mezi 10 a více městy
1)menu programu
2)načtení dat z textového souboru do pole a výpis na obrazovku
3)určení počátečního a koncového uzlu
4)výpis nejkratší cesty
5)zápis cesty do textového souboru jako pořadí uzlů
6)konec
*/
#include<stdio.h>
#include<conio.h>
#include<process.h>
#include<string.h>
#include<math.h>
#define IN 99
#define N 6

int dijsktra(int hodnota[][N],int pocatek,int cil)
{
int vzdalenost[N],prev[N],vybrano[N]={0},i,m,min,start,d,j;
char cesta[N];

    for(i=1;i< N;i++)
    {
        vzdalenost[i] = IN;
        prev[i] = -1;
    }
start = pocatek;
vybrano[start]=1;
vzdalenost[start] = 0;
    while(vybrano[cil] ==0)
    {
        min = IN;
        m = 0;
        for(i=1;i< N;i++)
        {
            d = vzdalenost[start]+hodnota[start][i];
            if(d< vzdalenost[i]&&vybrano[i]==0)
            {
                vzdalenost[i] = d;
                prev[i] = start;
            }
            if(min>vzdalenost[i] && vybrano[i]==0)
            {
                min = vzdalenost[i];
                m = i;
            }
        }
        start = m;
        vybrano[start] = 1;
    }
    start = cil;
    j = 0;
    while(start != -1)
    {
       cesta[j++] = start+65;
        start = prev[start];
    }
    cesta[j]='\0';
    strrev(cesta);
    printf("%s", cesta);
}

main()
{

int hodnota[N][N],i,j,w,co;
int pocatek,cil,x,y;
int pocet,akce;
FILE *fd;

do
 {
    printf("\n\n******  MENU  *******\n\n");
    printf("\n\nZvol jednu z techto moznosti:\n\n");
    printf("1 - Nacteni dat ze souboru\n");
    printf("2 - Urceni pocatecniho a konceveho uzlu\n");
    printf("3 - Zapis cesty do textoveho souboru jako poradi uzlu\n");
    printf("0 - KONEC programu\n\n");
    printf ("povel:");
    scanf ("%d",&akce);
  
    switch (akce)
 {
     case 1:
    printf("Provadim akci 1\n\n");
 
    for(i=1;i<N;i++)
    for(j=1;j<N;j++)
    hodnota[i][j] = IN;
    
    if((fd=fopen("uzly.txt","r"))==NULL);
    
	fscanf(fd,"%d",&pocet);  
    printf(" %d\n",pocet);
    
    for(x=1;x<pocet;x++)
    {
        for(y=x+1;y<N;y++)
        { 
            fscanf(fd,"%d",&w);
            hodnota [x][y] = hodnota[y][x] = w;
            printf("[%d][%d] = [%d][%d]= %d\n",x,y,y,x,w);
        }
        printf("\n");
    }
    break;
      
	  case 2:
    printf("Provadim akci 2\n\n");
    printf("\nZadejte pocatecni uzel: ");
    scanf("%d", &pocatek);
    printf("\nzadejte cilovy uzel: ");
    scanf("%d", &cil);
    co = dijsktra(hodnota,pocatek,cil);
    printf("\nNejkratsi trasa je: %d",co);
    fclose(fd);		
	break;
		
	 case 3:
	 printf("Provadim akci 3\n\n");
	 fd=fopen("uzly1.txt","w");
	 fprintf(fd,"Nejkratsi trasa je: ""%ld",co);
	 fclose(fd);
	 break;	   
  
	default:
	printf("Chybny povel\n\n");	 	
  }  
 }
   while (akce!=0);
printf("Konec programu\n\n");
system("PAUSE");
}

 

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032021 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý