.:: Bots United ::.  
filebase forums discord server github wiki web
cubebot epodbot fritzbot gravebot grogbot hpbbot ivpbot jkbotti joebot
meanmod podbotmm racc rcbot realbot sandbot shrikebot soulfathermaps yapb

Go Back   .:: Bots United ::. > Developer's Farm > General Programming
General Programming Help others and get yourself helped here!

Reply
 
Thread Tools
Dijkstra, Branch & Bound, Floyd pathfinding demo
Old
  (#1)
Whistler
Summoner
 
Whistler's Avatar
 
Status: Offline
Posts: 1,499
Join Date: Feb 2004
Location: Mist Village
Default Dijkstra, Branch & Bound, Floyd pathfinding demo - 25-11-2004

Branch & Bound:
PHP Code:
#include <stdio.h>
#include <stdlib.h>

int paths[5][5] = {
    {-
132, -156, -1},
    {-
1, -161, -1, -1},
    {
6167, -16191},
    {-
1, -112, -167},
    {
21, -1, -181, -1}
};

typedef struct node_s {
    
int       i;
    
node_s   *parent;
    
node_s   *next;
    
int       cost;
node_t;
    
main()
{
    
int fromto;
    
printf("Enter start point: ");
    
scanf("%d", &from);
    
printf("Enter end point: ");
    
scanf("%d", &to);
    
    
node_t *queue NULL, *closed NULL;
    
    
queue = new node_t;
    
queue->from;
    
queue->cost 0;
    
queue->parent NULL;
    
queue->next NULL;

    while (
queue) {
        
node_t *current queue;

        if (
current->== to) {
            
node_t *queue;
            
            while (
p) {
                
printf("%d, "p->i);
                
p->parent;
            }
            
printf("\n");
            goto 
endprogram;
        }

        
queue queue->next;

        for (
int i 05i++) {
            if (
paths[current->i][i] < 0)
                continue;

            
node_t *curchild = new node_t;
            
curchild->parent current;
            
curchild->i;
            
curchild->cost current->cost paths[current->i][i];

            
node_t *queue, *prev NULL;

            while (
&& p->cost curchild->cost) {
                
prev p;
                
p->next;
            }

            if (
prev) {
                
curchild->next p;
                
prev->next curchild;
            } else {
                
curchild->next queue;
                
queue curchild;
            }
        }

        if (
closed) {
            
closed->next current;
            
current->next NULL;
        } else {
            
closed current;
        }        
    }
    
    
printf("No path found!\n");

endprogram:
    while (
queue) {
        
node_t *queue->next;
        
delete queue;
        
queue p;
    }

    while (
closed) {
        
node_t *closed->next;
        
delete closed;
        
closed p;
    }

Dijkstra:
PHP Code:
#include <stdio.h>
#include <stdlib.h>

int paths[5][5] = {
    {-
132, -156, -1},
    {-
1, -161, -1, -1},
    {
6167, -16191},
    {-
1, -112, -167},
    {
21, -1, -181, -1}
};

typedef struct node_s {
    
int       i;
    
node_s   *parent;
    
node_s   *next;
    
int       cost;
node_t;
    
main()
{
    
int fromto;
    
printf("Enter start point: ");
    
scanf("%d", &from);
    
printf("Enter end point: ");
    
scanf("%d", &to);
    
    
node_t *open NULL, *closed NULL;
    
    
open = new node_t;
    
open->from;
    
open->cost 0;
    
open->parent NULL;
    
open->next NULL;

    while (
open) {
        
node_t *current open;

        if (
current->== to) {
            
node_t *open;
            
            while (
p) {
                
printf("%d, "p->i);
                
p->parent;
            }
            
printf("\n");
            goto 
endprogram;
        }

        
open open->next;

        for (
int i 05i++) {
            if (
paths[current->i][i] < 0)
                continue;

            
node_t *curchild = new node_t;
            
curchild->parent current;
            
curchild->i;
            
curchild->cost current->cost paths[current->i][i];

            
node_t *open, *prev NULL;
            
bool is_continue true;

            while (
p) {
                if (
p->== curchild->&& p->cost <= curchild->cost) {
                    
delete curchild;
                    
is_continue false;
                    break;
                }
                
p->next;
            }
            if (!
is_continue)
                continue;

            
closed;
            
is_continue true;
            while (
p) {
                if (
p->== curchild->&& p->cost <= curchild->cost) {
                    
delete curchild;
                    
is_continue false;
                    break;
                }    
                
p->next;
            }
            if (!
is_continue)
                continue;

            
open;
            while (
&& p->cost curchild->cost) {
                
prev p;
                
p->next;
            }

            if (
prev) {
                
curchild->next p;
                
prev->next curchild;
            } else {
                
curchild->next open;
                
open curchild;
            }
        }

        if (
closed) {
            
closed->next current;
            
current->next NULL;
        } else {
            
closed current;
        }        
    }

    
printf("No path found!\n");

endprogram:
    while (
open) {
        
node_t *open->next;
        
delete open;
        
open p;
    }

    while (
closed) {
        
node_t *closed->next;
        
delete closed;
        
closed p;
    }

Floyd-Warshall:
PHP Code:
#include <stdio.h>
#include <stdlib.h>

int paths[5][5] = {
    {
032, -156, -1},
    {-
1061, -1, -1},
    {
616706191},
    {-
1, -112067},
    {
21, -1, -1810}
};

main()
{
    
int path_matrix[5][5];
    
int dist_matrix[5][5];

    
int ijk;

    for (
05i++) {
        for (
05j++) {
            if (
paths[i][j] != -1) {
                
path_matrix[i][j] = j;
                
dist_matrix[i][j] = paths[i][j];
            } else {
                
path_matrix[i][j] = -1;
                
dist_matrix[i][j] = 32767;
            }    
        }
    }

    for (
05i++) {
        for (
05j++) {
            for (
05k++) {
                if (
dist_matrix[j][i] + dist_matrix[i][k] < dist_matrix[j][k]) {
                    
path_matrix[j][k] = i;
                    
dist_matrix[j][k] = dist_matrix[j][i] + dist_matrix[i][k];
                }
            }
        }
    }

    
printf("Enter start point: ");
    
scanf("%d", &i);
    
printf("Enter end point: ");
    
scanf("%d", &j);

    if (
dist_matrix[i][j] == 32767) {
       
printf("NO PATH FOUND !\n");
       exit(
1);
    }

    
printf("Total cost = %d; Path is: "dist_matrix[i][j]);
    while (
!= j) {
        
printf("%d, "i);    
        
path_matrix[i][j];
    }

    
printf("%d\n"j);

  
Reply With Quote
Re: Dijkstra, Branch & Bound, Floyd pathfinding demo
Old
  (#2)
Pierre-Marie Baty
Roi de France
 
Pierre-Marie Baty's Avatar
 
Status: Offline
Posts: 5,049
Join Date: Nov 2003
Location: 46°43'60N 0°43'0W 0.187A
Default Re: Dijkstra, Branch & Bound, Floyd pathfinding demo - 25-11-2004

Very interesting, and very useful. Be sure to check out this one also.



RACC home - Bots-United: beer, babies & bots (especially the latter)
"Learn to think by yourself, else others will do it for you."
  
Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump



Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
vBulletin Skin developed by: vBStyles.com