Dijkstrův algoritmus – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama

Dijkstrův algoritmus – C / C++ – Fórum – Programujte.comDijkstrův algoritmus – C / C++ – Fórum – Programujte.com

 
Hledat
Moderní platforma pro vytvoření vašeho nového webu – Wix.com.
Nyní už můžete mít web zdarma.
Vybavení pro Laser Game
Spuštěn Filmový magazín
Laser Game Brno
Laser Game Ostrava

Michal
~ Anonymní uživatel
651 příspěvků
15. 12. 2016   #1
-
0
-

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");
}
Nahlásit jako SPAM
IP: 93.99.96.–
Staon0
Návštěvník
19. 12. 2016   #2
-
0
-

#1 Michal
Takhle zběžným pohledem (pouze Dijkstra, menu a načítání vstupních dat jsem neřešil) mi připadá, že by to mělo, až na pár dost podstatných vad, fungovat. Není to sice zrovna nejefektivnější implementace Dijsktry, ale měla by být funkční. Ty podstatné vady jsou:

  • zvětšete si výrazně hodnotu pro nekonečno,
  • pole vybrano inicializujte v cyklu stejně jako pole vzdalenostprev,
  • v C se pole indexují od 0. Pokud máte for(i = 1; i < N; ++i), pak jste zapomněl projít první prvek a proiterujete pouze N - 1 prvků. Tahle chyba se vám vyskytuje všude včetně načítání vstupních dat.

Vzhledem k tomu, že v zadání máte "10 a více", tak výpis uzel + 65 nemůže fungovat. Místo charového pole si pro cestu udělejte intové pole a pomocí printf("%d") ji pak pozpátku vypište.

Nahlásit jako SPAM
IP: 94.142.234.–
peter
~ Anonymní uživatel
3485 příspěvků
19. 12. 2016   #3
-
0
-

Z pohledu lajka, ktery nevi o 'Dijkstrův algoritmus' vubec nic, resim nejkratsi cestu tak, ze si ...
- z herni plochy vygeneruji seznam policek a jejich sousedu, pole S. s[0] = [0, null, 1, 8, null] (na sachovnici nahore nic, vpravo pole 1, dole pole 8, vlavo nic - smery jsou podle hodinovych rucicek)
- pak zjistim existenci bodu A a B v poli (v php je to isset($s[$a])), aby mi tam treba nekdo nezadal neexist bod
-
x = []
x[] = [a, null] // pridam prvni,
y = 0 // pridam vsechny sousedy prvniho policka
x[] = [s[x[y]][0], y]
x[] = [s[x[y]][2], y] //sx0-1,3 neexistuje, ty nepridam
y++ // pridam sousedy sousedu
x[] = [s[x[y]][0], y] atd
atd, dokud nenarazim na bod B. Pak mam na vyber, kdy program ukoncim a zpetne vratim seznam policek. Nebo pokracuji jeste pro vsechny sousedy a pak nahodne vybiram trasu.

Nikdy jsem to neresil z tabulky vzdalenosti. Tam je to asi podobne. Jenom navic musis scitat vzdalenost a kdyz narazis na bod B najit ze vsech poslednich dat tu nejkratsi.

Nahlásit jako SPAM
IP: 2001:718:2601:26c:4db3:a9...–
Staon0
Návštěvník
19. 12. 2016   #4
-
0
-

#3 peter
Bohužel to tak nefunguje. Když se omezím pouze na šachovnici (což je méně obecné, než vyžaduje zadání), tak je potřeba si uvědomit, že nejkratší cesta nemusí nutně být také nejkratší na počet posunů na šachovnici (hran v grafu). Ve skutečnosti, pokud správně ohodnotíte hrany, vám nejkratší cesta může oběhnout několikrát šachovnici dokola nebo se různě kroutit apod. Takže pokud vámi popsaným algoritmem dosáhnete bodu B, v žádném případě nemáte jistotu, že jste našel nejkratší cestu.

Nahlásit jako SPAM
IP: 94.142.234.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 63 hostů

Podobná vlákna

Implementace - Dijkstrův algoritmus — založil Petr Pavlíček

Algoritmus — založil LuckaH

Algoritmus — založil Jirina.K

C++ algoritmus — založil silent

Algoritmus — založil RePRO

Moderátoři diskuze

 

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