wyznaczanie najkrótszej linii przez zadane punkty

Witam serdecznie.
Musze niapisac program, który wyznacza najkrótszą drogę przez zadane punkty. Oto polecenie:
"Należy napisać program wyznaczający najkrótszą linię przechodzącą przez
zadane punkty. Liczbę punktów i ich współrzędne podajemy na wejściu (np. z
pliku). Odpowiedzią na zadanie może być rysunek lub zapis do pliku - kolejności
łączonych punktów."

Częśc kodu już mam i napisałem go w ten sposób ,że z pliku tekstowego wczytuje wartości poszczególnych punktów do tablicy i wypisuje współrzędne na ekranie. I tu jestem w kropce bo nie wiem jak napisac skrypt, który by mi obliczał tę drogę. Dodam jeszcze, że pracuje na DEV c++ i nie jestem mocny z programowania. Bardzo proszę o pomoc

1. Poczytaj o algorytmie wyznaczania najkrotszej sciezki, np. na wikipedii
2. Do implementacji tego algorytmu bedziesz musial przeksztalcic punkty w graf i obliczyc wagi miedzy punktami. Wagami moze byc odleglosc miedzy nimi.

Pytanie ile jest punktow?

To chyba bez grafów i najkrótszej drogi się nie obejdzie.

DzieX napisał(a)

To chyba bez grafów i najkrótszej drogi się nie obejdzie.

No właśnie czytałem troche o tych grafach i powiem że jak dla mnie to brzmi to troche groźnie. Nie wiem czy mam racje ale czy Algorytm Dijkstry tu nie będzie przydatny. A jeśli tak to jak go prosto zailmplementowac??

//BADANIA OPERACYJNE - wyklad: 13.01.2001 r.
//SHORTEST PATH by DIJKSTRA
//rozwiazanie problemu najkrotszej sciezki metoda Dijkstra

#include <conio.h>
#include <iostream.h>

//definicja stalej - Dostatecznie Duza Liczba
const int DDL = 9999;
//realizujemy program na duzej tablicy, tablice alokowane dynamicznie
//bardzo by skomplikowaly czytelnosc programu
const int MAX = 30;
//poniewaz tablice w jezyku C sa indeksowane od zera, program operuje na
//pomniejszonych - i tak w procedurach miasto nr 1 jest traktowane jako
//miasto nr 0 - nie ma to jednak wplywu na wyniki dzialania programu.
void main(void)
{
char klawisz;				//sprawdzanie jaki klawisz zostal nacisniety
int ile_w;					//ilosc wierzcholkow
int siec[MAX][MAX];		//nasza siec zapisana jako tablica n*n
int T[MAX];					//do jakiego zbioru nalezy wierzcholek(0 - S, 1 - T)
int TJ[MAX];				//oszacowane odleglosci
int poprzednik[MAX];		//poprzedniki wierzcholkow
int sciezka[MAX];			//najkrotsza sciezka
int petla0, petla1;		//zmienne pomocnicze - petle
int start; 					//punkt startowy
int koniec;					//punkt koncowy
int ostatni;				//ostatni analizowany wierzcholek;
int s_ost;					//odleglosc od punktu startowego
int minimum;            //zmienna pomocnicza - szukamy minimalnej drogi
int pozycja;            //zmienna pomocnicza - j.w. ele interesuje nas miasto

//wprowadzanie ilosc wierzcholkow
clrscr();
cout << "Wprowadz ilosc wierzcholkow (<" << MAX <<"): ";
cin >> ile_w;

cout << "Wprowadz odleglosci pomiedzy wierzcholkami" << endl;
cout << "Jesli wierzcholkami nie maja polaczenia wpisz \"0\"" << endl << endl;
//wprowadzamy odleglosci miedzy wierzcholkami, automatycznie zapisujac DDL
//dla tego samego wierzcholka. Aby uproscic wpisywanie danych pozwalamy na
//wpisywanie zera, jesli wierzcholki nie maja polaczenia - program
//automatycznie zamienia je na DDL
for(petla0 = 0; petla0 < ile_w; petla0++)
	for(petla1 = 0; petla1 < ile_w; petla1++)
		{
		if(petla0 == petla1) siec[petla0][petla1] = DDL;
			else
			{
			cout << "Wprowadz odleglosc z miasta "
				<< (petla0 + 1) << " do miasta " << (petla1 + 1) << " : ";
			cin >> siec[petla0][petla1];
			if(siec[petla0][petla1] == 0)
				siec[petla0][petla1] = DDL;
			}
		}

do
	{
	clrscr();
	cout << "Wprowadz punkt startowy: "; cin >> start;
	cout << "Wprowadz punkt koncowy: "; cin >> koniec;

	//ustawianie wartosci poczatkowych
	//ustawiamy ostatni wierzcholek na starowy i poczatkowa odleglosc
	start--; koniec--; ostatni = start; s_ost = 0;
	//ustawiamy elementy zbioru T i wartosci oszacowane
	for(petla0 = 0; petla0 < ile_w; petla0++)
		{
		T[petla0] = 1;
		TJ[petla0] = DDL;
		}
	T[start] = 0;
	TJ[start] = 0;
	poprzednik[start] = DDL;

	do
		{
		//dla kazdego wierzcholka nalezacego do T staramy sie poprawic oszacowanie
		for(petla0 = 0; petla0 < ile_w; petla0++)
			{
			if((T[petla0])&& ((s_ost + siec[ostatni][petla0]) < TJ[petla0]))
				{
				TJ[petla0] = s_ost + siec[ostatni][petla0];
				poprzednik[petla0] = ostatni;
				}
			}
		//realizacja pomniejszania zbioru T
		minimum = DDL;
		for(petla0 = 0; petla0 < ile_w; petla0++)
			{
			if((T[petla0])&& (TJ[petla0] < minimum))
				{
				minimum = TJ[petla0];
				pozycja = petla0;
				}
			}
		T[pozycja] = 0;
		ostatni = pozycja;
		s_ost = TJ[ostatni];
		}
		while(T[koniec] == 1);
	//wypisanie wynikow na ekran
	//najpierw musimy odczytac z tabeli wlasciwa kolejnosc
	pozycja = 0; ostatni = koniec;
	do
		{
		sciezka[pozycja++] = ostatni;
		ostatni = poprzednik[ostatni];
		}
		while(ostatni != DDL);
	//i mozemy wypisac wszystkie dane na ekran
	cout << endl << "Rozwiazaniem jest sciezka: ";
	for(petla0 = (pozycja - 1); petla0 >=0; petla0--)
		cout << "[" << (sciezka[petla0] + 1) << "]";
	cout << endl << "O dlugosci: " << s_ost;
	//czy jeszcze inna sciezka
	cout << endl << endl << "Czy chcesz zbadac inna sciezke? [T/N]";
	klawisz = getch();
	}
	while((klawisz != 'n') && (klawisz != 'N'));
}

To jest to co udało mi sie do tej pory napisac:

#include <cstdlib>
#include <iostream>
#include <string>
#include <conio.h>
#include <fstream>

using namespace std;

ifstream plik_we;
string nazwa_pliku;

typedef struct { int x;
                 int y; } SPunkt;

void otworz_plik() {
do {
cout << "nazwa pliku do otwarcia: ";
cin >> nazwa_pliku;
plik_we.open(nazwa_pliku.c_str());
}
while (!plik_we.is_open());
plik_we.clear();
};

void menu() {
char wybor;
cout << "w jakiej formie dane maja byc wczytywane?" << endl;
cout << "[P] - z pliku" << endl;
cout << "[M] - wpisywane recznie" << endl;
cout << "Twoj wybor: ";
cin >> wybor;
wybor=toupper(wybor);
while ((wybor!='P')&&(wybor!='M')) {
cout << "Zly wybor! Podaj jeszcze raz: ";
cin >> wybor;
wybor=toupper(wybor);
};

 switch (wybor) {
        case 'P': otworz_plik(); break;
        case 'M': cout << "M"; break;
                };
        };
 


          

int ile_wierszy() {
int ilew=0;
string ltmp;
plik_we.clear();
while (!plik_we.eof()) {getline(plik_we,ltmp); ilew++;};
plik_we.close();
plik_we.open(nazwa_pliku.c_str());
plik_we.clear() ;
return ilew;

              };

int main(int argc, char* argv[])
{

menu();
int ile=ile_wierszy();

SPunkt wektor[ile];

int tmp=0;
do {
plik_we >> wektor[tmp].x >> wektor[tmp].y;
tmp++;
}
while (!plik_we.eof());

for (int tmp=0; tmp<ile; tmp++) {
cout << wektor[tmp].x << " ";
cout << wektor[tmp].y << endl;
};

plik_we.close();
getch();

}

Czy mógłby ktoś poświęcic chwilkę pomóc mi go dokończyc?
Będę wdzięczny za najmniejszą pomoc

problem komiwojażera