C Programming

Project description:

ABC company is a big courier company that transports packages from one town to another. The management recently decided to cut down its transportation expenses by asking drivers to travel through the shortest path from one town to another town. So you are hired to develop a program that finds the shortest path between two towns.
You will be given the number of towns (n) and a 2-dimensional n x n distnace matrix that denotes the distance of the roads between towns. Following is an example of a 5 x 5 matrix.
0 inf inf 10 3 inf 0 9 7 5 inf 9 0 inf inf 10 7 inf 0 1 3 5 inf 1 0
if the matrix[r , c] is not inf then there is a road between rth town and cth town. As an example in the above matrix there are roads between 0th town and 3rd town, 0th town and 4th town, 1st town and 2nd town etc. assuming the number of the first town is 0 and so on. Diagonal of the matrix is always 0 as it represents the same town. As you notice the matrix is symmetric (mirror reflection around diagonal axis) because if there is a road between a and b that means there is a road between b and a for the same cost as well.
Your task is to find the shortest path between two towns. Bonus Part. Print the list of towns in the shortest path from starting town to the destination town.
Note: Instead of inf you can use 2147483647 ( which is the maximum number in int category) and you can assume that cost of any actual path ( or set of paths) is less than 2147483647.

I did a similar project, but using the distance vector algorithm

Do you still have the source code? I pretty much have everything written except I cant think of how to scan through the distance matrices to find paths and figure out which one is the shortest. I'm thinking about creating a boolean array with all false values then scan through the matrix and store all non false values in a matrix then add up all those distances and find the lowest values based on all the paths it could find. Easier said than done though.

>>59497200
Do your homework yourself.

File: djikstras.gif (842KB, 724x720px) Image search: [Google]

842KB, 724x720px

I wrote it in Java.

File: 1488836949080.jpg (346KB, 1800x1200px) Image search: [Google]

346KB, 1800x1200px

>>59499840
Share the code man

>>59499840
This satisfies my autism

>>59499840
The A* gif is more satisfying.

File: A_star.gif (99KB, 904x904px) Image search: [Google]

99KB, 904x904px

>>59500320
>>59500347
With a proper heuristic, it's a lot faster.

>>59500480
This one is odd, what's the heuristic, just going for the closest tile in absolute distance each time? Why doesn't it go diagonally through the opening in (2,2)?

I'm an electrical engineering student I have no idea why I'm in a C programming course, but hey here I am. and I'm not even a smart EE student so this is extra cumbersome. Most people just cheat and get the CSE people to write their projects for them. I actually want to learn the language though so my programs usually come out like 50 lines longer than everyone else's and aren't very efficient. Thought maybe one of you gurus could lend some advice but shit posters will shit post.

>>59497200
kys you worthless sack of shit.

>>59500544
Dijkstra is not that hard. Do you somehow have a clue of what to do or does it sound like a foreign language to you? Doing it on a matrix may be less intuitive than doing it in a graph and nodes OOP structure, but still, if you read the dikstra wiki page you'll be alright.

>>59499840
what is this blue stuff and why is it needed when start and end points are already marked?

>>59500656
Bitch do you even /dijkstra/?

blue is visited tiles
cyan is unvisited tiles still in queue

once the destination has been visited and that no unvisited tiles still lead to it, the search ends.

>>59500544
where are you from? Just curious where do EEs do C

>>59500685
Well thanks.First time I see this stuff. So its basically the bunch of automated if conditions? Is it hard?

>>59499777
/thrrrrrrrrr

File: LIT 3.gif (944KB, 500x281px) Image search: [Google]

944KB, 500x281px

>>59499840
I didn't know Lightning ran off of Djikstra's algorithm.

>>59500737
It's basically just a simple queue-based flood fill only each "pixel" keeps track of its length from the start so you can retrace your steps backwards.

>>59500819
its the other way around, djikstra didnt invent natural phenomenon(not to mention that two are totally unrelated , its just they look similar)

public class Atv {
public static void main(String[] args) {
final int SIZE = 5;
int[][] map = new int[SIZE][SIZE];

for (int i = 0; i < SIZE; i++) Arrays.fill(map[i], Integer.MAX_VALUE);

map[0][1] = 30;
map[0][2] = 20;
map[2][1] = 5;

int[] dist = dijkstra(0, map);
for (int i = 0; i < dist.length; i++) System.out.printf("%d -> %d\n", i, dist[i]);
}

/**
* Returns every distante from origin.
**/
public static int[] dijkstra(int origin, int roads[][]) {
int size = roads.length;

int[] dist = new int[size];
boolean[] visit = new boolean[size];

Arrays.fill(dist, Integer.MAX_VALUE); // Every town is unreachable
Arrays.fill(visit, false); // Every town was not visited

dist[origin] = 0; // There's a distante to origin: 0!

for (int i = 0; i < size; i++) {
int org = getNext(dist, visit); // get the minimum known distante

visit[org] = true; // mark that as visited

for (int to = 0; to < size; to++) { // for all possible destinations

if (roads[org][to] < Integer.MAX_VALUE // must have a road
&& dist[org] < Integer.MAX_VALUE // must have a path until here
&& !visit[to] // must be not visited
&& dist[org] + roads[org][to] < dist[to] /* the distante must be shorter */) {
dist[to] = dist[org] + roads[org][to]; // update distante
}
}
}

return dist;
}

/* just find the minimum not visited distante */
public static int getNext(int[] dist, boolean[] visit) {
int minIndex = 0;
int minDist = Integer.MAX_VALUE;

for (int i = 0; i < dist.length; i++) {
if (dist[i] < minDist && !visit[i]) {
minIndex = i;
minDist = dist[minIndex];
}
}

return minIndex;
}
}

>>5950120
> java
> but you need something like this
> adapt to C

>>59500819
this gif is nice

>>59500519
Diagonal distance is a PITA to do since your distance now has to be a float, so most implementations just assume nesw movement only.

You need:
* a set S of unprocessed nodes
* a heap H of candidates
* a stack P of steps

A candidate is a triplet (n, l, p) where n is your node, p the previous node in the shortest path to n found yet and l is the length of the shortest path from the start to n. Candidates are ordered by l.

A step is a couple (n, p) where n is a node and p is the previous node in the shortest path from the start to n.

First, all your nodes are in S. Take the start s and put (s, 0) in H.

For each iteration, take the candidate (n, l, p) at the top of H and for each node n' in S accessible from it, add (n', l + w) to H where w is the weight of the arc from n to n'. Then take the candidate (n', l', p') at the top of H and put it back again, updated if a shorter path to n' through n exists. Finally, add (n, l, p) to the stack P.

Stop when the heap H is empty or the top of the stack contains the destination.

In the former case, no path exists.

In the latter case, you get the path by following the previous nodes (p) from the top down to the start.

Dijkstra becomes almost trivial when you picture it with the proper data structures.

>>59497212
your professor is retarded, just use -1 for inf

>>59500204
Here's the meat of it. The rest of the project is just Swing code.

        while (!open.isEmpty()) {
            //get and remove the head
            Node current = open.poll();
            current.setState(Node.State.EVALUATED);
            //move it to the closed list
            closed.add(current);

            //iterates through neighboring nodes
            for (Node neighbor : current.getNeighbors()) {
                //if the neighbor is our goal, build the path and return it
                if (neighbor.equals(goal)) {
                    neighbor.setParent(current);
                    return constructPath(start, neighbor);
                }
                //node is obstacle or it's already been evaluated, skip it
                if (neighbor.isBlocked() || closed.contains(neighbor)) {
                    continue;
                }
                //known distance from start to current + calculated distance from current to neighbor
                double cost = current.g_cost + current.distanceTo(neighbor);
                // distance is less than known distance for the neighbor node
                if (!open.contains(neighbor) || cost < neighbor.g_cost) {
                    //set its parent to the current node
                    neighbor.setParent(current);
                    //set its known distance
                    neighbor.g_cost = cost;
                    //set the heuristic distance
                    neighbor.f_cost = neighbor.g_cost + heuristic.cost(modifier, neighbor, goal);
                    //add neighbor to open list, if it isn't there already (next to be evaluated)
                    if (!open.contains(neighbor)) {
                        neighbor.setState(Node.State.QUEUED);
                        open.add(neighbor);
                    }
                }
        }

>>59500819
This image is awesome. Still, is this the best nature can do? It tried to find ground in the sky lol

>>59500819
literally everything is just fractal algorithms slamming into one another

>>59501359
Not really, you can go with integers for diagonals.

This is how I do it in my game with d1 being 5 and d2 being 7:

const uint32_t DiagonalDistance(const sf::Vector2i &from, const sf::Vector2i &to, const uint32_t &d1, const uint32_t &d2)
{
    const auto &dx = std::abs(from.x - to.x);
    const auto &dy = std::abs(from.y - to.y);

    return d1 * (dx + dy) + (d2 - 2 * d1) * std::min(dx, dy);
}

>>59499840
>>59500480
I want to write one of these in C, what's the easiest way to make an animated gif from a bunch of buffers?

File: wrong.jpg (490KB, 1170x744px) Image search: [Google]

490KB, 1170x744px

>>59500480
But your algo here is wrong. Where I circled in pic related there is a blue pixel that you should have taken because that is the shortest way around it, but instead your algo just goes around it. Watch the animation to see what I mean. Found the same bug at least 3 times...

How could that be fixed?

Thanks /g I'll post a pic of the final code it's actually pretty short now that I've cut out the test functions and other useless garbage. One thing I don't understand is how to define a function of passed by reference variables. Such as
Void set_path(argc[][], I, j)
And get it to return an array. I know returning an entire array isn't possible so I've just returned the values of I and j. But there's gotta be a better way.

>>59507026
There is no guarantee that you find the shortest path when you use that type of heuristic.

You can either tweak it or say you accept the solution despite not being optimal.

>>59509078
but the first gif is supposed to be slower but optimal?

>>59509143
First is Slower to find, optimal shortest distance.

Second is quicker, not always optimal.

You show both to management or product owner, do some time analysis, pick whichever one fits this business need.