Mam napisać program, który umożliwia znalezienie najkrótszej trasy miedzy dwoma miastami. Miasta połączone są drogami o pewnej długości. Drogi są jednokierunkowe. Plik mapy dróg ma nastepujaca postac:
W każdej linii podana jest jedna droga:
miasto początkowe i miasto końcowe i odległości
Przykładowy plik dróg (liczba dróg nie jest ograniczona):
Kod: Zaznacz cały
Katowice Krakow 70
Krakow Tarnow 70
Tarnow Jaslo 50
Katowice Gliwice 22
Lodz Poznan 205
Gliwice Katowice 22
Katowice Czestochowa 70
Czestochowa Lodz 120
Lodz Torun 165
Krakow Katowice 70
Gliwice Wroclaw 180postaci:
miasto początkowe i miasto końcowe
Przykładowy plik tras do wyznaczenia (liczba tras nie jest ograniczona):
Kod: Zaznacz cały
Katowice Toruń
Kraków Poznań
Tarnów Wrocławcałkowita długość, a potem poszczególne odcinki z długościami, np.
Kod: Zaznacz cały
trasa: Katowice --> Toruń (355 km):
Katowice --> Częstochowa 70
Częstochowa --> Lodź 120
Lodź --> Toruń 165
trasa: Krakow --> Poznan (465 km):
Krakow --> Katowice 70
Katowice --> Czestochowa 70
Czestochowa --> Lodz 120
Lodz --> Poznan 205
trasa: Tarnow --> Wroclaw
TRASA NIEMOZLIWA DO WYZNACZENIAjest dowolna):
-d plik wejściowy z drogami
-t plik wejściowy z trasami do wyznaczenia
-o plik wynikowy z wyznaczony trasami
To mam :
Kod: Zaznacz cały
Program mapa;
Uses Crt;
Const
M = 1000000;
Type
Dane = //plik z drogami
Record
mp : String;
mk : String;
odl : Integer;
End;
Szukane =
Record
mp : String;
mk : String;
End;
pelist=^elist;
elist=record
inf : dane;
a1,a2,a3,a4,a5 : pelist;
End;
dBaza = Array [0..M-1] Of Dane; // Tablica z danymi
sBaza = Array [0..M-1] Of Szukane; // Tablica z szukanymi
pl1 = File Of Dane; // Typ pliku zawierajĄcego dane
pl2 = File Of Szukane; // Typ pliku zawierajĄcego szukane
Var
Baza1 : dBaza;
Baza2 : sBaza;
Ilosc,Ilosc2 : Word;
Wybor : Char; { Zmienna pomocnicza dla menu }
Procedure menu;forward;
{ - Wejcie i wyjcie ------------------------------------------------------ }
Procedure Wczytaj(I: Word); { Wczytywanie rekordu o indeksie I }
Begin
If (I<Ilosc) Then { Typ Word i tak nie zawiera wartoci ujemnych }
With Baza1[I] Do { Do tego suľy instrukcja wiĄľĄca }
Begin
WriteLn('Podaj: ', I, ':');
Write('Miasto poczĄtkowe ');
If (mp<>'') Then Write('[', mp, '] ');
ReadLn(mp);
Write('Miasto koäcowe: ');
If (mk<>'') Then Write('[', mk, '] ');
ReadLn(mk);
Write('Odlego†: ');
If (odl<>0) Then Write('[', odl, '] ');
ReadLn(odl);
End;
End;
Procedure Wypisz(I: Word); // Wypisywanie rekordu o indeksie I
Begin
If (I<Ilosc) Then
With Baza1[I] Do
Begin
Write(' ', I, '. ');
Write(mp, ' - ', ' ', mk);
Write(' : ',odl);
WriteLn;
End;
End;
{ - Wejcie i wyjcie koniec ----------------------------------------------- }
{ - Operacje na danych ----------------------------------------------------- }
Procedure Pokaz; //Pokazuje zakres rekord˘w z pliku
Var
I, Ia : Word;
Begin
Write('Podaj g˘rnĄ granic© [', M, ' dla wszystkich rekord˘w]... ');
ReadLn(Ia);
WriteLn;
For I:=0 To Ia Do
Wypisz(I);
End;
Procedure Edytuj; //Suľy do edycji danego rekordu danych
Var
I : Word;
Begin
Write('Podaj indeks rekordu, kt˘ry chcesz edytowa†... ');
ReadLn(I);
WriteLn;
Wczytaj(I);
If (I>=Ilosc) Then
WriteLn('Taki rekord nie istnieje - nie moľesz go edytowa†.');
End;
Procedure Dodaj; //Dodaje, a nast©pnie pozwala na edycj© rekordu
Begin
Inc(Ilosc); // Zwi©kszamy ilo† danych w bazie
WriteLn;
Wczytaj(Ilosc-1); // Edytujemy ostatni rekord
End;
Procedure Usun; // Procedura usuwa pewien zakres rekord˘w
Var
I, Ia, Ib, Il : Word;
Begin
Write('Podaj dolnĄ granic© indeks˘w danych, kt˘re chcesz usunĄ†... ');
ReadLn(Ia);
Write('Podaj g˘rnĄ granic©... ');
ReadLn(Ib);
If (Ia<Ilosc) And (Ib<Ilosc) And (Ib>=Ia) Then
Begin
Il:=Ib-Ia+1;
For I:=Ib+1 To Ilosc-1 Do
Baza1[I-Il]:=Baza1[I];
For I:=Ilosc-Il To Ilosc-1 Do
With Baza1[I] Do
Begin
mp:='';
mk:='';
odl:=0;
End;
Dec(Ilosc, Il);
End
Else
WriteLn('Nieprawidowe granice - nie moľna usunĄ† rekord˘w.');
End;
{ - Operacje na danych koniec ---------------------------------------------- }
{ - Operacje na plikach ---------------------------------------------------- }
Procedure Otworz; //??????????????????????????????????????????????????????
Var
F : pl1;
Begin
Assign(F,'C:/ABC/dan.txt.');
Reset(F); { Przygotowujemy plik do odczytu }
While (Not EoF(F)) Do { EoF(F: File) zwraca True jeli jestemy }
Begin { na koäcu pliku }
Read(F, Baza1[Ilosc]); { Czytamy zmiennĄ z pliku F }
Inc(Ilosc);
End;
Close(F); { Na koniec zamykamy plik }
End;
Procedure Zapisz;
Var
F : pl1;
I : Word;
Begin
Assign(F,'C:/ABC/dan.txt.');
ReWrite(F);
For I:=0 To Ilosc-1 Do
Write(F, Baza1[I]);
Close(F);
End;
//--------------------Operacje na szukanych
//**********************************************************************
Procedure Wczytaj2(I: Word); { Wczytywanie rekordu o indeksie I }
Begin
If (I<Ilosc2) Then { Typ Word i tak nie zawiera wartoci ujemnych }
With Baza2[I] Do { Do tego suľy instrukcja wiĄľĄca }
Begin
WriteLn('Podaj: ', I, ':');
Write('Miasto poczĄtkowe ');
If (mp<>'') Then Write('[', mp, '] ');
ReadLn(mp);
Write('Miasto koäcowe: ');
If (mk<>'') Then Write('[', mk, '] ');
ReadLn(mk);
End;
End;
Procedure Wypisz2(I: Word); // Wypisywanie rekordu o indeksie I
Begin
If (I<Ilosc2) Then
With Baza2[I] Do
Begin
Write(' ', I, '. ');
Write(mp, ' - ', ' ', mk);
WriteLn;
End;
End;
{ - Wejcie i wyjcie koniec ----------------------------------------------- }
{ - Operacje na danych ----------------------------------------------------- }
Procedure Pokaz2; //Pokazuje zakres rekord˘w z pliku
Var
I, Ia : Word;
Begin
Write('Podaj g˘rnĄ granic© [', M, ' dla wszystkich rekord˘w]... ');
ReadLn(Ia);
WriteLn;
For I:=0 To Ia Do
Wypisz2(I);
End;
Procedure Edytuj2; //Suľy do edycji danego rekordu danych
Var
I : Word;
Begin
Write('Podaj indeks rekordu, kt˘ry chcesz edytowa†... ');
ReadLn(I);
WriteLn;
Wczytaj2(I);
If (I>=Ilosc2) Then
WriteLn('Taki rekord nie istnieje - nie moľesz go edytowa†.');
End;
Procedure Dodaj2; //Dodaje, a nast©pnie pozwala na edycj© rekordu
Begin
Inc(Ilosc2); // Zwi©kszamy ilo† danych w bazie
WriteLn;
Wczytaj2(Ilosc2-1); // Edytujemy ostatni rekord
End;
Procedure Usun2; // Procedura usuwa pewien zakres rekord˘w
Var
I, Ia, Ib, Il : Word;
Begin
Write('Podaj dolnĄ granic© indeks˘w danych, kt˘re chcesz usunĄ†... ');
ReadLn(Ia);
Write('Podaj g˘rnĄ granic©... ');
ReadLn(Ib);
If (Ia<Ilosc2) And (Ib<Ilosc2) And (Ib>=Ia) Then
Begin
Il:=Ib-Ia+1;
For I:=Ib+1 To Ilosc2-1 Do
Baza2[I-Il]:=Baza2[I];
For I:=Ilosc2-Il To Ilosc2-1 Do
With Baza2[I] Do
Begin
mp:='';
mk:='';
End;
Dec(Ilosc2, Il);
End
Else
WriteLn('Nieprawidowe granice - nie moľna usunĄ† rekord˘w.');
End;
{ - Operacje na danych koniec ---------------------------------------------- }
{ - Operacje na plikach ---------------------------------------------------- }
Procedure Otworz2; //??????????????????????????????????????????????????????
Var
F : pl2;
Begin
Assign(F,'C:/ABC/szuk.txt.');
Reset(F);
While (Not EoF(F)) Do
Begin
Read(F, Baza2[Ilosc2]);
Inc(Ilosc2);
End;
Close(F);
End;
Procedure Zapisz2;
Var
F : pl2;
I : Word;
Begin
Assign(F,'C:/ABC/szuk.txt.');
ReWrite(F);
For I:=0 To Ilosc2-1 Do
Write(F, Baza2[I]);
Close(F);
End;
Procedure wyzdroge;
begin
end;
//listyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
Procedure licz;
var
x,y,a:string;
i,j:integer;
tab2,tab:array of dane;
begin
For i:=0 to (ilosc2-1) do
begin
x:=Baza2[I].mp; //szukane miasto poczatkowe
y:=Baza2[I].mk; //szukane miasto koncowe
Finalize(tab);
readln;
menu;
end;
end;
Procedure koniec;
begin
halt;
end;
//------------Menu z danymi-----------------------------
Procedure menu1;
begin
Repeat
ClrScr;
WriteLn;
writeLn('Dane');
WriteLn('Co chcesz zrobi†?');
WriteLn(' 1. Pokaza† rekord(y)');
WriteLn(' 2. Edytowa† rekord');
WriteLn(' 3. Doda† nowy rekord');
WriteLn(' 4. UsunĄ† rekord(y)');
WriteLn(' 5. Zapisa† prac© i wr˘ci† do g˘wnego menu');
Write('Tw˘j wyb˘r [1-5]... ');
ReadLn(Wybor);
WriteLn;
Case (Wybor) Of
'1' : Pokaz;
'2' : Edytuj;
'3' : Dodaj;
'4' : Usun;
'5' : { Nic };
Else WriteLn('Nie ma takiej opcji');
End;
writeln('Nacisnij enter aby kontynuowa†.');
readln;
Until (Wybor='5');
Zapisz;
menu;
end;
//------------Menu z szukanymi-----------------------------
Procedure menu2;
begin
Repeat
ClrScr;
WriteLn;
WriteLn('Szukane');
WriteLn('Co chcesz zrobi†?');
WriteLn(' 1. Pokaza† rekord(y)');
WriteLn(' 2. Edytowa† rekord');
WriteLn(' 3. Doda† nowy rekord');
WriteLn(' 4. UsunĄ† rekord(y)');
WriteLn(' 5. Zapisa† prac© i wr˘ci† do g˘wnego menu');
Write('Tw˘j wyb˘r [1-5]... ');
ReadLn(Wybor);
WriteLn;
Case (Wybor) Of
'1' : Pokaz2;
'2' : Edytuj2;
'3' : Dodaj2;
'4' : Usun2;
'5' : { Nic };
Else WriteLn('Nie ma takiej opcji');
End;
writeln('Nacisnij enter aby kontynuowa†.');
readln;
Until (Wybor='5');
Zapisz2;
menu;
end;
//-------------Menu G˘wne------------------------
Procedure menu;
begin
Repeat
ClrScr;
WriteLn;
WriteLn('Co chcesz zrobi†?');
WriteLn(' 1. Modyfikowa† plik z drogami');
WriteLn(' 2. Modyfikowa† plik z szukanymi');
WriteLn(' 3. Wyznaczy† drogi');
WriteLn(' 4. koniec');
Write('Tw˘j wyb˘r [1-4]... ');
ReadLn(Wybor); { Wyb˘r uľytkownika }
WriteLn;
Case (Wybor) Of
'1' : menu1;
'2' : menu2;
'3' : licz;
'4' : koniec;
Else WriteLn('Nie ma takiej opcji');
End;
Until (Wybor='4');
end;
{ - Operacje na plikach koniec --------------------------------------------- }
Begin
Ilosc:=0;
Ilosc2:=0;
Otworz;Otworz2;
menu;
End.
Proszę o pomoc . Bardzo proszę
A tak na poważnie, wiesz jak dziala ten algorytm? U Ciebie kazde miasto to wierzcholek a krawedzie to drogi miedzy nimi o odpowiednich wagach tutaj odległość w km. Pomocne może okazać się dla Ciebie wpisanie w google 'i lo tarnów dijkstra' i pierwszy odnośnik. Tylko nie wiem czemu u mnie strona się nie chce załadować :/ Ale kiedyś sam z niej korzystałem piszac program własnie opierajacy sie na tym algorytmie.