Looking for Your Help on dijkstra algorithm Post: 302578018

Sponsored Content

Top Forums Programming Looking for Your Help on dijkstra algorithm Post 302578018 by ali2011 on Wednesday 30th of November 2011 01:59:12 PM

11-30-2011

Registered User

Looking for Your Help on dijkstra algorithm

Can you help to adjust the void dijkstra(int s) function to find a path from source to every node so that the minimum cost on that path is maximum.
Ex:
From 1 to 2 we have 1 - 3 - 4 - 2 , costs(2+3+4+5)
From 1 to 2 we have 1 - 5 - 6 - 2 , costs(3+3+4+5)
I need the algorithm to choose path 1 - 5 - 6 - 2 since minimum cost = 3 > minimum cost in the first path.

======= Here is the code I'm looking to adjust ======

Code:

#include <stdio.h>

#define GRAPHSIZE 2048
#define INFINITY GRAPHSIZE*GRAPHSIZE
#define MAX(a, b) ((a > b) ? (a) : (b))

int e; /* The number of nonzero edges in the graph */
int n; /* The number of nodes in the graph */
long dist[GRAPHSIZE][GRAPHSIZE]; /* dist[i][j] is the distance between node i and j; or 0 if there is no direct connection */
long d[GRAPHSIZE]; /* d[i] is the length of the shortest path between the source (s) and node i */
int prev[GRAPHSIZE][GRAPHSIZE + 1]; /* prev[i] holds the nodes that could comes right before i in the shortest path from the source to i;
                                        prev[i][0] is the number of nodes and prev[i][1..] are the nodes */

void printD() {
    int i;

    printf("Distances:\n");
    for (i = 1; i <= n; ++i)
        printf("%10d", i);
    printf("\n");
    for (i = 1; i <= n; ++i) {
        printf("%10ld", d[i]);
    }
    printf("\n");
}

/*
 * Prints the shortest path from the source to dest.
 *
 * dijkstra(int) MUST be run at least once BEFORE
 * this is called
 */
void printPath(int dest, int depth) {
    int i, j;

    printf("-%d\n", dest);
    for (i = 1; i <= prev[dest][0]; ++i) {
        for (j = 0; j <= depth; ++j)
            printf(" |");
        printPath(prev[dest][i], depth + 1);
    }
}

void dijkstra(int s) {
    int i, k, mini;
    int visited[GRAPHSIZE];

    for (i = 1; i <= n; ++i) {
        d[i] = INFINITY;
        prev[i][0] = 0; /* no path has yet been found to i */
        visited[i] = 0; /* the i-th element has not yet been visited */
    }

    d[s] = 0;

    for (k = 1; k <= n; ++k) {
        mini = -1;
        for (i = 1; i <= n; ++i)
            if (!visited[i] && ((mini == -1) || (d[i] < d[mini])))
                mini = i;

        visited[mini] = 1;

        for (i = 1; i <= n; ++i)
            if (dist[mini][i]) {
                if (d[mini] + dist[mini][i] < d[i]) { /* a shorter path has been found */
                    d[i] = d[mini] + dist[mini][i];
                    prev[i][0] = 1;
                    prev[i][1] = mini;
                } else if (d[mini] + dist[mini][i] == d[i]) { /* a path of the same length has been found */
                    ++prev[i][0];
                    prev[i][prev[i][0]] = mini;
                }
            }
    }
}

int main(int argc, char *argv[]) {
    int i, j;
    int u, v, w;

    FILE *fin = fopen("dist.txt", "r");
    fscanf(fin, "%d", &e);
    for (i = 0; i < e; ++i)
        for (j = 0; j < e; ++j)
            dist[i][j] = 0;
    n = -1;
    for (i = 0; i < e; ++i) {
        fscanf(fin, "%d%d%d", &u, &v, &w);
        dist[u][v] = w;
        n = MAX(u, MAX(v, n));
    }
    fclose(fin);

    dijkstra(1);

    printD();

    printf("\n");
    for (i = 1; i <= n; ++i) {
        printf("Path to %d:\n", i);
        printPath(i, 0);
        printf("\n");
    }

    return 0;
}

ali2011

View Public Profile for ali2011

Find all posts by ali2011

9 More Discussions You Might Find Interesting

1. Programming

Feedback algorithm

Hi I search an exemple of scheduling Feedback algorithm, or help about how to create one. Thanks

2. Solaris

Help in Search Algorithm

I am tryin to change the sort fields in mainframes to the equivalent in Unix. I have a large datafile of which i extract only the specified fields ... cut them ... write it into another file with a delimiter... and sort based on these fields... then match these fields to those from input file ......

3. Shell Programming and Scripting

algorithm

PID USERNAME SIZE RSS STATE PRI NICE TIME CPU PROCESS/NLWP 21444 tomusr 213M 61M sleep 29 10 1:20:46 0.1% java/43 21249 root 93M 44M sleep 29 10 1:07:19 0.2% java/56 is there anyway i can use a command to get the total of the SIZE? 306M (Derive from...

4. UNIX for Advanced & Expert Users

Algorithm In Pseudocode

A) produce an algorithm in pseudocode and a flowchart that gets n from the user and calculate their sum. B) Write an algorithm in pseudocode and a flowchart that gets number x from he user and calculates x5 ( X to the power of %5). Calculate by using multiplication. ...

5. Programming

Please help me to develop algorithm

Hi guys , in my study book from which I re-learn C is task to generate all possible characters combination from numbers entered by the user. I know this algorithm must use combinatorics to calculate all permutations. Problem is how to implement algortihm. // This program reads the four numbers...

6. Homework & Coursework Questions

Heuristic Algorithm Example

Give a counter example such that the following heuristic algorithm, for the 2-tape problem, doesn't always produce the best solution: Algorithm: Sort {Xi} in descending order. Place files in tapes one at a time. For a file being considered, assign the file to the smaller tape. Thanks in...

7. UNIX for Dummies Questions & Answers

banker's algorithm.. help

i'm doing banker's algorithm.. got some error there but i cant fix it.. please help!! #!/bin/bash echo "enter no.of resources: " read n1 echo -n "enter the max no .of resources for each type: " for(( i=0; i <$n1; i++ )) do read ${t} done echo -n "enter no .of...

8. Homework & Coursework Questions

Banker's algorithm

Use and complete the template provided. The entire template must be completed. If you don't, your post may be deleted! 1. The problem statement, all variables and given/known data: shell scripts to simulate Banker’s algorithm on a collection of processes (process details are entered as inputs...

9. Shell Programming and Scripting

Masking algorithm

I have a requirement of masking few specific fields in the UNIX file. The details are as following- File is fixed length file with each record of 250 charater length. 2 fields needs to be masked – the positions are 21:30 and 110:120 The character by character making needs to be done which...

LEARN ABOUT OPENSOLARIS

di_path_client_next_path

di_path_client_next_path(3DEVINFO)		       Device Information Library Functions			di_path_client_next_path(3DEVINFO)

NAME

       di_path_client_next_path, di_path_phci_next_path - libdevinfo path node traversal functions

SYNOPSIS

       cc [ flag... ] file... -ldevinfo [ library... ]
       #include <libdevinfo.h>

       di_path_t di_path_client_next_path(di_node_t node node,
	    di_path_t path);

       di_path_t di_path_phci_next_path(di_node_t node node,
	    di_path_t path);

PARAMETERS

       node    The  handle  to	a device node in a di_init(3DEVINFO) snapshot.	For di_path_client_next_path(), node must be a client device node.
	       For di_path_phci_next_path(), node must be a pHCI device node.

       path    DI_PATH_NIL, or the handle to a path node in a snapshot.

DESCRIPTION

       Each path node is an element in a pHCI-client matrix. The matrix is implemented by dual linked lists: one list links path nodes related	to
       a common client head, and the other links path nodes related to a common pHCI head.

       The  di_path_client_next_path()	function  is called on a multipathing 'client' device node, where a 'client' is the child of a vHCI device
       node, and is associated with a specific endpoint device	identity  (independent	of  physical  paths).	If  the  path  argument  is  NULL,
       di_path_client_next_path()  returns  the  first	path  node  associated	with  the client. To walk all path nodes associated with a client,
       returned di_path_t values are fed back into di_path_client_next_path(), via the path argument, until a null path  node  is  returned.   For
       each path node, di_path_bus_addr(3DEVINFO) returns the pHCI child path node unit-address.

       The  di_path_phci_next_path() function is called on a multipathing pHCI device node. If the path argument is NULL, di_path_phci_next_path()
       returns the first path node associated with the pHCI. To walk all path nodes associated with a pHCI, returned di_path_t values are fed back
       into  di_path_phci_next_path(),	via  the path argument, until a null path node is returned.  For each path node, di_path_client_node(3DEV-
       INFO) provides a pointer to the associated client device node.

       A device node can be a client device node of one multipathing class and a pHCI device node of another class.

RETURN VALUES

       Upon successful completion, a handle to the next path node is returned. Otherwise, DI_PATH_NIL is returned and errno is set to indicate the
       error.

ERRORS

       These functions will fail if:

       EINVAL	  One or more argument was invalid.

       ENOTSUP	  Path node information is not available in the snapshot.

       ENXIO	  The end of the path node list was reached.

ATTRIBUTES

       See attributes(5)  for descriptions of the following attributes:

       +-----------------------------+-----------------------------+
       |      ATTRIBUTE TYPE	     |	    ATTRIBUTE VALUE	   |
       +-----------------------------+-----------------------------+
       |Interface Stability	     |Committed 		   |
       +-----------------------------+-----------------------------+
       |MT-Level		     |Safe			   |
       +-----------------------------+-----------------------------+

SEE ALSO

       di_init(3DEVINFO), di_path_bus_addr(3DEVINFO), di_path_client_node(3DEVINFO), libdevinfo(3LIB), attributes(5)

       Writing Device Drivers

SunOS 5.11							    15 May 2008 				di_path_client_next_path(3DEVINFO)