ΥڡϤƤʥ֥åޡɲΥڡޤϤƤʥ֥åޡ Υڡlivedoor åפɲΥڡޤlivedoor å

ܼ

ûϩ

դλޤˤϡ°ȤƿͤͿ뤳Ȥ롣οͤΤȤŤߡweightȤνŤߤ2֤ΥȤĹʤɤ̣뤳Ȥ¿

դ2֤ϩΤǡŤߤ¤ǾȤʤƻûϩȤϡƻϩ֤ˤ2֤εΥκǾͥ͡åȥ֤̿βˡʤɡϰϤϹ

ǹͤΤϡŤߤդͭդǤ롣

ûϩΥ르ꥺ

ȥˡ

ȥˡDijkstra's algorithmϡûϩɽŪʥ르ꥺΰǤ롣Ūʹͤϡؤκûϩȯ˶ᤤȤ顢缡ꤷƤˡǤ롣

դ˵ΥդŤդͭվǤդ2֤κûΥᡢǽŪˤϤ٤ƤؤκûΥ륢르ꥺǤ롣٤ˤ缡éäƤŪ˻ꤷȯᤫؤκûΥ롣

[]ȥˡΤȲꤷ꤬ܾ䥽ճʤɤλˤ褯ꤵƤ롣

㡧ΥդˤơȥˡȤäơv1ؤκûΥ롣

ȥˡǺûΥˤϡȯκûΥΤ狼äƤνSȡS˴ޤޤ뤤줫ܤνSζȸƤ֡ˤˤĤƺûΥ˴ؤͻäʤ顢S˴ޤޤ䤷ơ٤ƤФûΥƤ

1ޤSˤϽȯǤv1ޤޤƤȤƹͻʤ롣ξ硢Sζv2,v3,v43롣줾εΥ8,5,3Ǥ롣κûΥv1v43ʤΤǡv4򿷤S˴ޤ뤳Ȥˤʤ롣

2S={v1,v4}ʤΤǡSζ{v2,v3}Ȥʤ롣SSζκûΥͤʷͳ⤢뤳Ȥաˡv1ΥȤȤľܤεΥ8,5Ǥ뤬v4ͳv1v4v2ʵΥ75+2ˡv1v4v3ʵΥ43+1ˤȤʤ롣κûΥv1v4v3εΥ4Ǥ롣äơv3S˲ä롣

3S={v1,v3,v4}ʤΤǡSζ{v2}Ȥʤ롣v2ޤǤεΥ롣v1v2ʵΥ8ˡv1v3v2ʵΥ7ˡv1v4v3v2ʵΥ6ˤʤΤǡûΥ6Ǥꡢv1v4v3v2פûΥȤʤϩˤʤ롣

ʸ

  • إեȥȯѼԡʥå󥷥ϥɥ֥å
  • إեȥȯѼԻкԥ塼­ܸ齬