Графтар теориясының негізгі анықтамалары Қолдану мысалдары
жүктеу/скачать 291,42 Kb.
|
23-24 Графтар 1
- Бұл бет үшін навигация:
- Дейкстр алгоритмі
- Дейкстр алгоритмі нәтижесінде d және post массивтерінің жаңа мәнін аламыз: Бұл 0-2 төбелерінің
| Дейкстр алгоритмі
Үшінші логикалық типтегі массивте графтың таңдалған (тұрақты) төбелері жазылады. Алғашында графтың «тұрақты» төбесі ретінде бірінші төбе ғана белгіленеді (t[0]). Одан кейін «уақытша» төбе таңдалады, бірінші (тұрақты) төбеден осы төбеге дейінгі аралық ең қысқа болуы керек. Осы төбе k төбесі болып жарияланады. Графтың «тұрақты» төбесінен барлық «уақытша» төбеге дейінгі барлық маршруттар тікелей және k төбесі арқылы тексеріледі. Ең қысқа аралықтар екінші массивке жазылады. Ал, егер ең қысқа арақашықтықтың маршруты k төбесі арқылы өтетін болса, онда бірінші массивке сәйкес позицияда k жазылады. Ары қарай k төбесі «тұрақты» болып жарияланады (ол үшінші массивте орындалады). Графтың келесі төбесін іздеу алгоритмі жаңа «тұрақты» төбеге қатысты қайталанады. Дейкстр алгоритмі Бірінші төбенің нөмері 0-ге тең деп жорамалдайық. Онда post[…]-бірінші массив нөлдерден тұрады. Екінші массивте, яғни ең қысқа қышықтықтар массивінде сыбайлас матрицаның нөлінші жолының мәндері жазылады: Үшінші масссив, яғни таңдап алынған (выбранный) төбелер массивінің мәндері true болады, тек нөлінші элементте ғана t[0]=false;. 0-ші төбеден басқа бір төбеге дейінгі ең қысқа аралықты таңдаймыз. Біздің жағдайымызда ол 1-ші төбе болады, оған дейінгі қашықтық 3-ке тең болады. Таңдап алынған төбе k деп аталсын. Флойд алгоритмін қолданып, алғашқы төбеден “k” төбесі арқылы өтетін қалған басқа төбелерге дейінгі барлық ең қысқа маршруттарды табамыз. for (j=0;j<9;j++) if ((t[j]==true)&&(d[j]>d[k]+a[k,j])) { d[j]=d[k]+a[k,j]; post[j]=k; } Дейкстр алгоритмі нәтижесінде d және post массивтерінің жаңа мәнін аламыз: Бұл 0-2 төбелерінің арасындағы ең қысқа арақашықтық 7-ге тең болатынын білдіреді, маршрут 1-і төбе арқылы өтеді. Таңдап алынған k төбесін t[k]=false «тұрақты» деп жариялаймыз және осы төбеге қатысты процесс қайталанып отырады. Дейкстр алгоритмі жүктеу/скачать 291,42 Kb. Достарыңызбен бөлісу:
|