Looking for Your Help on dijkstra algorithm


 
Thread Tools Search this Thread
Top Forums Programming Looking for Your Help on dijkstra algorithm
# 1  
Old 11-30-2011
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;
}

# 2  
Old 11-30-2011
Adjust in what way? What's it doing right now? If it's not working, in what way is it not working?

Is this homework?
# 3  
Old 11-30-2011
A minute and will post an input file and the correct source code if the problem is clear for you. Normal Dijkstra gives you the shortest path between any two nodes in terms of let's say loss rate. Basicly, it shows you how you can transfer data between two nodes with less delay (you can add delay between nodes 1, 5, 6, and 2 (see e.g., in first post) to be the total; so the current code shows you between any two nodes in your network where is the path with minimum delay). BUT I want to adjust this to give me the best path in terms of capacity (since capacity is not addiditve quantity (it's limited by the minimum capacity on that path; you can't add capacities between nodes 1, 5, 6, and 2 and say Dijkstra will give minimum capacity as in delay; It's the opposite in here since we need capacity to be the larger, but of course limited by the minimum capacity between 1 and 5, which is 3). Therefore, I need Dijkstra to tell me what is the best path that has minimum capacity grater than others as mentioned in my previous post.

---------- Post updated at 03:06 PM ---------- Previous update was at 02:49 PM ----------

No it's not a HW problem; it's related to an experiment I'm doing.
# 4  
Old 11-30-2011
You asked.

Do not use link-state algorithms (like dijkstra) or distance vector alogrithms (like Bellman-Ford) for an inter-domain problem. There are serious problems with them once you leave a domain; they work okay inside a domain only.

Before you waste your time see if RFC 1322 isn't what you want:
RFC 1322 - A Unified Approach to Inter-Domain Routing

It has links to algorithms I think.
# 5  
Old 11-30-2011
I have seen some indicators that say Dijkstra can do the job after adjustments, but not that strong in c programming.

EE122 Introduction to Computer Networks Department of Electrical
Login or Register to Ask a Question

Previous Thread | Next Thread

9 More Discussions You Might Find Interesting

1. 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... (5 Replies)
Discussion started by: n78298
5 Replies

2. 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... (4 Replies)
Discussion started by: syah
4 Replies

3. 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... (1 Reply)
Discussion started by: syah
1 Replies

4. 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... (1 Reply)
Discussion started by: sureshcisco
1 Replies

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... (0 Replies)
Discussion started by: solaris_user
0 Replies

6. 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. ... (1 Reply)
Discussion started by: delsega
1 Replies

7. 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... (5 Replies)
Discussion started by: filthymonk
5 Replies

8. 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 ...... (1 Reply)
Discussion started by: bourne
1 Replies

9. Programming

Feedback algorithm

Hi I search an exemple of scheduling Feedback algorithm, or help about how to create one. Thanks (0 Replies)
Discussion started by: messier79
0 Replies
Login or Register to Ask a Question