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

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 :)

#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)

#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).