Boost GraphのダイクストラとA*の速度を比較してみた

最短経路が短めの場合はダイクストラの方が速いが、長めの場合はA*の方が速いという結果になった。

ビルド

要g++, boost

$ make

実行

$ ./shortest_path 520 9999
Graph loaded: vertices: 264347, edges: 733846
START: 520, GOAL: 9999
### Dijkstra
   520    519    528    530    516    630    629    681    645    640    639    637    635    636    625    339    338    337    320    343    297    294    295    196    202    181   4503   4502   4739   4735   4733   4730   4725   4724   4723   4701   4699   4639   4638   4640   4617   4481   4482   4480   4467   4464   4461   4463   4456   4429   4428   4430   4420   4427   4426   4423   4425   4412   4436 259696 259692 259691 258332 258330 258314 258313 258312 244615 244579 244582 244581 244592 244589 244555 244551 244540 244538 244537 244524 244519 244523 244520 244513 244512 244486 243796 243806 243804 243803 243801 243741 243737 243736 243710 243709 243713 243691 243706 243686 243705 243704 261405 261223 243409 243408 243410 243405 243403 243402 243400 243392 243394 261331 261330 244845 244841 244840 244833 244818 244830 244700 244697 244696 244695 244677 244648 244646 244664 244645 244643 244642 244641 263393 244635 244637 241119 241113 241101 241102 241048 241009 240993 240217 261433 240989 240988 240987 261435 240605 240604 240583 240078 240079 240039 240037 263715 240033 240020 240019 239208 233430 233429 233427 233428 234707 233270 233271 233447 233452 233453 233461 233463 233483 233470 233468 233471 233486 233485 233488 233494 233490 233479 233478 233481 233466 233467 233474 233532 233535 233538 233537 233552 233557 233553 233550 233554 233549 232893 232860 232925 232923 232911 232910 232908 232906 232905 232898 232896 232838 232835 232836 232831 232832 232826 232825 232828  10043  10042  10044  10023  10024   7253   7254   7290   7291  10019  10016  10027  10010  10008  10009   9997  10002  10003   9993  10000   9998   9999
Time: 0.0182049 sec
### A*
   520    519    528    530    516    630    629    681    645    640    639    637    635    636    625    339    338    337    320    343    297    294    295    196    202    181   4503   4502   4739   4735   4733   4730   4725   4724   4723   4701   4699   4639   4638   4640   4617   4481   4482   4480   4467   4464   4461   4463   4456   4429   4428   4430   4420   4427   4426   4423   4425   4412   4436 259696 259692 259691 258332 258330 258314 258313 258312 244615 244579 244582 244581 244592 244589 244555 244551 244540 244538 244537 244524 244519 244523 244520 244513 244512 244486 243796 243806 243804 243803 243801 243741 243737 243736 243710 243709 243713 243691 243706 243686 243705 243704 261405 261223 243409 243408 243410 243405 243403 243402 243400 243392 243394 261331 261330 244845 244841 244840 244833 244818 244830 244700 244697 244696 244695 244677 244648 244646 244664 244645 244643 244642 244641 263393 244635 244637 241119 241113 241101 241102 241048 241009 240993 240217 261433 240989 240988 240987 261435 240605 240604 240583 240078 240079 240039 240037 263715 240033 240020 240019 239208 233430 233429 233427 233428 234707 233270 233271 233447 233452 233453 233461 233463 233483 233470 233468 233471 233486 233485 233488 233494 233490 233479 233478 233481 233466 233467 233474 233532 233535 233538 233537 233552 233557 233553 233550 233554 233549 232893 232860 232925 232923 232911 232910 232908 232906 232905 232898 232896 232838 232835 232836 232831 232832 232826 232825 232828  10043  10042  10044  10023  10024   7253   7254   7290   7291  10019  10016  10027  10010  10008  10009   9997  10002  10003   9993  10000   9998   9999
Time: 0.0199516 sec