Forum » Programiranje » [C++] Pomoč pri nalogi razveji in omeji
[C++] Pomoč pri nalogi razveji in omeji

Matic1911 ::
Pozdravljeni!
Prosil bi za pomoč pri naslednji nalogi.
Navodila:
Za predstavitev grafa bomo tudi tukaj uporabili matriko sosednosti C.
Psevdokod samega algoritma je naslednji:
Algoritem v izpisu 1 ima pet parametrov, tri vhodne in sicer G predstavlja podatke o
grafu, s izhodiščno vozlišče, g pa ciljno vozlišče. Zadnja dva parametra sta izhodna
parametra. V spremenljivki R vrnemo najdeno najkrajšo pot, v spremenljivki
cena_resitve pa ceno te najkrajše poti. Predstavljeni algoritem
RAZVEJI_IN_OMEJI najde vse poti z isto ceno. V ta namen služi funkcija
DODAJ_RESITEV, ki k trenutno poti doda novo pot z isto ceno. Funkcija
VSTAVI_NOVO_RESITEV počisti vrsto z rešitvijo in vstavi novo pot. Funkcija
DODAJ_VOZLISCE zadnjemu vozlišču v poti doda novo vozlišče. Pot hranimo v
statičnem polju. Če določenih povezav v grafu ni, to označimo z vrednostjo 9999.
Moja koda:
Problem je v tem, da nevem kako naj nadaljujem.
Hvaležen bom vsake pomoči.
LP
Prosil bi za pomoč pri naslednji nalogi.
Navodila:
Za predstavitev grafa bomo tudi tukaj uporabili matriko sosednosti C.
Psevdokod samega algoritma je naslednji:
function RAZVEJI_IN_OMEJI(G, s, g, R, cena_resitve)
begin
pot.vozlisca := <s>
pot.dolzina := 0
R := prazna
cena_resitve := 9999
VSTAVI_V_VRSTO(Q, pot)
while not(PRAZNA(Q))
begin
p := VZAMI_IZ_VRSTE(Q)
u := zadnje vozlišče v poti p
for each vozlišče v EUR G.Sosedi(u) do
if not(v EUR p.vozlisca) then
begin
p1 := DODAJ_VOZLISCE(p, v)
p1.dolzina := p.dolzina + C[u,v]
if v = g then
begin
if p1.dolzina < cena_resitve then
VSTAVI_NOVO_RESITEV(R, p1)
else if p1.dolzina = cena_resitve then
DODAJ_RESITEV(R, p1)
end
else if p.dolzina < cena_resitve then
VSTAVI_V_VRSTO(Q, p1)
end
end
end
Algoritem v izpisu 1 ima pet parametrov, tri vhodne in sicer G predstavlja podatke o
grafu, s izhodiščno vozlišče, g pa ciljno vozlišče. Zadnja dva parametra sta izhodna
parametra. V spremenljivki R vrnemo najdeno najkrajšo pot, v spremenljivki
cena_resitve pa ceno te najkrajše poti. Predstavljeni algoritem
RAZVEJI_IN_OMEJI najde vse poti z isto ceno. V ta namen služi funkcija
DODAJ_RESITEV, ki k trenutno poti doda novo pot z isto ceno. Funkcija
VSTAVI_NOVO_RESITEV počisti vrsto z rešitvijo in vstavi novo pot. Funkcija
DODAJ_VOZLISCE zadnjemu vozlišču v poti doda novo vozlišče. Pot hranimo v
statičnem polju. Če določenih povezav v grafu ni, to označimo z vrednostjo 9999.
Moja koda:
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int MAX = 9999;
struct Pot// struktura Pot
{
vector<int> vozlisca;// vektor vozlisc
int dolzina;
};
Pot p;
int vel;
vector<Pot> Q;
vector<Pot> R;// resitev
int C[30][30];
int s;// zacetno vozlisce
int g;// koncno vozlisce
int cena_resitve;// cena
void beri(string f)
{
fstream dat(f.c_str(), fstream::in);
dat >> vel;
for(int i = 0; i < vel; i++)
{
for(int j = 0; j < vel; j++)
{
if(i == j)
{
C[i][j] = 0;
}
else
{
C[i][j] = MAX;
}
}
}
int i = 0;
int p;
int q;
int c;
while(!dat.eof())
{
dat >> p >> q >> c;
C[p-1][q-1] = c;
//C[q-1][p-1] = c;
i++;
}
dat.close();
}
void RazvejiInOmeji()
{
p.vozlisca.push_back(s);
p.dolzina = 0;
cena_resitve = 9999;
Q.push_back(p);
while(!Q.empty())
{
p = Q.back();
Q.pop_back();
int u = p.vozlisca.back();
for(int i = 0; i < vel; i++)
{
if(C[u][i] != MAX)
{// tukaj se zalomi
int main()
{
int izbira;
while(1)
{
cout << endl;
cout << "Razveji in omeji - izbira" << endl;
cout << endl;
cout << "1 Preberi podatke iz datoteke" << endl;
cout << "2 Iskanje poti med vozliscema s in g" << endl;
cout << "3 Konec" << endl;
cout << endl;
cout << "Vasa izbira: ";
cin >> izbira;
cout << endl;
switch(izbira)
{
case 1:
beri("graf.txt");
cout << "Velikost: " << vel << endl;
cout << endl;
for(int j = 0; j < vel; j++)
{
for(int i = 0; i < vel; i++)
{
cout << C[i][j] << " ";
}
cout << endl;
}
break;
case 2:
break;
case 3:
return 0;
break;
default:
break;
}
}
return 0;
}
Problem je v tem, da nevem kako naj nadaljujem.
Hvaležen bom vsake pomoči.
LP
- spremenil: Matic1911 ()
Vredno ogleda ...
Tema | Ogledi | Zadnje sporočilo | |
---|---|---|---|
Tema | Ogledi | Zadnje sporočilo | |
» | DIJKSTROV_ALGORITEMOddelek: Programiranje | 2271 (1505) | krneki0001 |
» | Kruskalov algoritem težave pri implementacijiOddelek: Programiranje | 1696 (1470) | zacetnik11 |
» | [C++ naloga] seznamOddelek: Programiranje | 1423 (1423) | BigWhale |
» | [c++] dvosmerno povezan seznamOddelek: Programiranje | 2617 (2453) | upirna |
» | pomoc pri skladuOddelek: Programiranje | 1393 (1318) | NoUse4AName |