Najkratsia cesta medzi vrcholmi stromu – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

Najkratsia cesta medzi vrcholmi stromu – C / C++ – Fórum – Programujte.comNajkratsia cesta medzi vrcholmi stromu – C / C++ – Fórum – Programujte.com

 

Adam K.
~ Anonymní uživatel
4 příspěvky
9. 12. 2016   #1
-
0
-

Ahojte, potreboval by som pomoc...mam zadany pocet vrcholov aj hran a suradnice jednotlivych vrcholov a dlzky hran a potrenujem vypocitat dlzku najkratsej cesty.

Mam hotove toto:  

// uloha-7-2.c -- Tyzden 7 - Uloha 2
// Adam Kotvas, 2.11.2016 13:43:06
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<stdlib.h>

int pv = 0;
int pole[22000][22000];
int najdi_vzdialenost(int ciel, int od, int v, int dlzka)
{
	dlzka += pole[od][v];
	int i, j = 1;
	for (i = v;; j++)
	{
		if (v == ciel) {
			return dlzka;
		}
		if (j > pv)
		{
			if (i == 1 && v != od) return 0;
			i = od;
			j = v;
			dlzka -= pole[v][od];
			continue;
		}
		if (pole[i][j] != 0)
		{
			if (j == od && v != od) continue;
			//dlzka = pole[i][j];

			return dlzka = najdi_vzdialenost(ciel, i, j, dlzka);
		}
	}
}
int main()
{
	int ph = 0, prvy, v, ciel, i, j, x = 0, y = 0, dlzka = 0;
	scanf("%d %d %d %d", &pv, &ph, &prvy, &ciel);
	/*
	int **pole = (int**)malloc((pv + 1) * sizeof(int*));
	for (i = 1; i <= pv; i++)
	{
	pole[i] = (int*)malloc((pv + 1)*(sizeof(int)));
	}
	for (i = 1; i <= pv; i++)
	for (j = 1; j <= pv; j++)
	{
	pole[i][j] = 0;
	}
	*/
	for (i = 1; i <= ph; i++)
	{
		scanf("%d %d %d", &x, &y, &dlzka);
		pole[x][y] = dlzka;
		pole[y][x] = dlzka;
	}
	dlzka = 0;
	for (i = 1; i < pv; i++)
	{
		if (pole[i][ciel] == 0) continue;
		else
		{
			printf("%d\n", najdi_vzdialenost(ciel, prvy, prvy, dlzka));
			break;
		}
	}
	if (i == pv) printf("-1");

	return 0;
}


problem je ze je to prilis pomale kedze pri velkych cislach to musi prehladavat cele pole niekolkokrat a je to dost neefektivne...vedeli by ste mi poradit ako to mam upravit aby to boo casovo efektivnejsie? Idealne bez pouzitia spajanych zoznamov kedze sa v nich zrovna nevyzivam :D

Dakujem :)

Nahlásit jako SPAM
IP: 195.212.29.–
KIIV
~ Moderátor
+43
God of flame
10. 12. 2016   #2
-
0
-

#1 Adam K.
Muzes pouzit zpusob ohodnocovani hran. Zacinas v pocatecni hrane ohodnocenem jako 0, a vsechny sousedni ohodnotis jako aktualni + delka strany (v pripade, ze bude vysledna hodnota mensi nez uz tam je). Koncis jak dosahnes cile a zaroven zadne nezpracovane hrany nejsou mensi nez nalezena nejkratsi vzdalenost (tezko najdes kratsi)

Ale prinejmensim fronte se nevyhnes.

A teoreticky muzes postupovat z obou smeru zaroven. ale je to trosku slozitejsi.

Jestli muzes, dej sem i testovaci data. Mohlo by byt zajimave si s tim pohrat (ikdyz asi az nekdy pozdeji a spis v C++, v C clovek furt dokola vynaleza kolo)

Nahlásit jako SPAM
IP: 93.91.151.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Staon0
Návštěvník
19. 12. 2016   #3
-
0
-

#1 Adam K.
Pokud máte nadpis správně a graf je skutečně strom, pak je situace dost jednoduchá. Ve stromu mezi dvěma vrcholy existuje právě jedna cesta. Takže stačí najít jakoukoliv cestu a ta je nejkratší. Pro tenhle účel bude asi nejsnažší prohledávání do hloubky (i když prohledávání do šířky je samozřejmě taky možné). Tzn. něco takového (psané naslepo, nemusí fungovat): 

int najdi_vzdalenost(int cil, int od, int v, int delka) {
  if(cil == v)
    return delka;

  /* -- zanor se do vsech sousedu krome toho, odkud jsi prisel */
  for(int i = 0; i < pv; ++i) {
    if(i != od && i != v && pole[v][i] != 0) {
      int d = najdi_vzdalenost(cil, v, i, delka + pole[v][i]);
      if(d >= 0)
        return d;
    }
  }

  return -1;
}

int vysledek = najdi_vzdalenost(cil, start, start, 0);

Algoritmus bude fungovat pouze na stromě, na jakémkoliv jiném grafu už je špatně.

Pro praktické použití moc není, protože na velkých grafech mu pravděpodobně přeteče zásobník. Navíc také máte naprosto nevhodnou reprezentaci grafu. V každém vrcholu se prochází v cyklu všechny ostatní vrcholy, takže celková časová složitost je O(n^2) (n je počet vrcholů). To je špatně. Pokud byste měl reprezentaci, kde se dá seznam sousedů dostat přímo (např. spojový seznam sousedů pro každý vrchol), mohl byste dosáhnout časové složitosti O(n + m), a protože počet hran ve stromu je m = n - 1, tak nakonec O(n).

Nahlásit jako SPAM
IP: 94.112.135.–
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, 9 hostů

Moderátoři diskuze

 

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