Ысқа жолды өту тапсырмасы.

Қысқа жол дегеніміз, S төбесін t төбесімен біріктіретін, мүмкін болатын маршруттардың минимальды ұзындығын қамтитын жол.

Жол – түйіндер мен тармақтардың кезектесулері болып табылатын маршруттар кешені.

Беріліс жолы біріншілік тарамда беріледі. Жол ұзындығы сандық түрде мынаған тең:

1. Барлық мүмкін болатын жолдар бұтағының қабырғалар санына;

2. Барлық аралық төбелер арасындағы қосынды арақашықтық болып табылатын, арақашықтыққа.

Қосымша тораптағы қабырғалардың минимальды санын қамтитын жол немесе түйіндер арасындағы арақашықытық минимальды болып табылатын жол қысқа жол болып табылады.

Минимальды салмақты қысқа жолды табу тапсырмасы салмақталған қабырғаларды қамтитын G графы үшін құрылады, яғни қабырғаларда С құнын белгілейтін, β сыйымдылығын белгілейтін салмақ беріледі немесе екі түйінді байланыстыратын каналдар санымен беріледі. Бұл тапсырма ПРИМА немесе ДЕЙКСТРА алгоритмдерінің көмегімен шешіледі. Бұл алгоритм (ПРИМА) келесі шарттар негізінде құрылады:

1. G графы берілген, қабырғасы W (i,j) белгілі бір салмаққа немесе ұзындыққа ие. Егер қабырға жоқ болса,онда W (i,j) мәні ∞ (0)-тең болады деп қабылданады.

2. S төбесінен t төбесіне дейінгі арақашықтық минимальды болу керек, және ең төбедегі бұл арақашықтық нөлге тең болып алынады.

d(S,t)→min,

d(i,i)=0

S₀ маршруты үшін минимальды жолды табу

. Ықшамдау шарты.

Ықшамдау шарты бүтінсандық программалау тәсілдерінде қолданылады.

Алгоритм:

1. Di, бұтағын құру, ол минимальды салмақтың қаңқасы болып табылады. Қаңқа – S түйінін t түйінімен байланыстырушы қабырғалардың минимальды санын қамтитын бұтақ.

2. Минимальды салмақты қабырғаны таңдап, минимальды қабырға үшін төбе құру.

3. Егер инцидентті түйінге дейін келесі минимальды қабырға кездессе, онда оны Di бұтағының ішінде құру қажет.

4. Егер i=n-1, онда қабырғалар саны бар, әрине, Dn-1 минимальды салмақты қаңқа құрылған, басқа жағдайда 2-қадамға көшу.

Минимальды салмақты есептеу үшін салмақтар матрицасын құру қажет.

M14={1, 2, 3, 4; 1, 2, 6, 4; 1, 5, 3, 4; 1, 5, 6, 4}

Не нашли, что искали? Воспользуйтесь поиском: