«Дискретті математика»
Алгоритмді орындауды аяқтау
жүктеу/скачать 445,27 Kb.
|
Дийкстра алгоритмі
- Бұл бет үшін навигация:
- Алгоритмді іске асыру коды
| Алгоритмді орындауды аяқтау.
Барлық шыңдарға барған кезде алгоритм аяқталады. Алгоритмнің нәтижесі соңғы суретте көрінеді: 1 төбесінен 2-ге дейінгі ең қысқа жол - 7, 3-ке - 9, 4-ке - 20, 5-ке - 20, 6-ға дейін - 11. Егер кез келген уақытта барлық қаралмаған шыңдар шексіздікпен белгіленсе, онда бұл бұл шыңдарға жету мүмкін емес дегенді білдіреді (яғни Граф ажыратылған). Содан кейін алгоритмді мерзімінен бұрын аяқтауға болады. Алгоритм Белгілер V — графтың төбелерінің жиыны E — Граф жиектерінің жиыны w[ij] — жиектің салмағы (ұзындығы) ij a — арақашықтықтар ізделетін шың U — көптеген шыңдарға шықты d[u] — алгоритмнің соңында а нүктесінен u нүктесіне дейінгі ең қысқа жолдың ұзындығына тең p[u] — алгоритмнің соңында a-дан u-ға дейінгі ең қысқа жолды қамтиды u — алгоритммен қарастырылатын ағымдағы шың Алгоритмді іске асыру коды Төменде Java бағдарламалау тілінде алгоритмді жүзеге асыру коды берілген. Бұл іске асыру нұсқасы ең жақсы емес, бірақ ол алгоритмнің мүмкін орындалуын анық көрсетеді: class Dijkstra { double[] dist = new double[GV()]; Edge[] pred = new Edge[GV()]; public Dijkstra(WeightedDigraph G, int s) { boolean[] marked = new boolean[GV()]; for (int v = 0; v MinPQplus pq = new MinPQplus dist[s] = 0.0; pq.put(dist[s], s); while (!pq.isEmpty()) { int v = pq.delMin(); if (marked[v]) continue; marked(v) = true; for (Edge e (v)) { int w = e.to(); if (dist[w]> dist[v] + e.weight()) { dist[w] = dist[v] + e.weight(); pred[w] = e; pq.insert(dist[w], w); } } Псевдокод Сәйкес келейік d[a]← 0, p[a]← 0 a-дан өзгеше барлық u ∈ V үшін d [u ]←∞ тағайындаймыз ∃v ∉U болған кезде v ∉ U ең аз d[v] төбесі болсын, v нүктесін U-ге қойыңыз. Барлық u ∉ U үшін vu ∈ E болатындай Егер d[u]>d[v]+w[vu] болса d[u]←d[v]+w[vu] өзгертейік p[u]← (p[v],u) өзгертейік Сипаттама Ең қарапайым іске асыруда d[i] сандарын сақтау үшін сандар массивін және U жиынындағы элементтің мүшелігін сақтау үшін логикалық айнымалылар массивін пайдалануға болады. Алгоритмнің басында бастапқы шыңға арналған қашықтық нөлге орнатылады, ал қалған барлық қашықтықтар үлкен оң санмен толтырылады (Графтегі максималды мүмкін жолдан үлкен). Жалаулар массиві нөлдермен толтырылған. Содан кейін негізгі цикл басталады. Циклдің әрбір қадамында біз шыңды іздейміз v ең аз қашықтық және жалауша нөлге тең. Содан кейін біз оның жалауын 1-ге орнатамыз және оған іргелес жатқан барлық u шыңдарын тексереміз. Егер оларда (u-де) қашықтық ағымдағы шыңға дейінгі қашықтық пен жиектің ұзындығының қосындысынан үлкен болса, онда біз оны азайтамыз. Цикл барлық шыңдардың жалаулары 1-ге тең болғанда немесе 0 жалаушасы бар барлық шыңдар d[i]=∞ болғанда аяқталады. Соңғы жағдай G графигі ажыратылған жағдайда ғана мүмкін болады. жүктеу/скачать 445,27 Kb. Достарыңызбен бөлісу:
|