Shortest distance

[daniel66]

I am writing a program to find the shortest distance from two separate points on a graph. After a bit of online research I think I might be trying to implement a Dijkstra algorithm but my instructor never called it that. I feel like I am starting to get off track when I include extra nodes for path comparisons. Any advice or just saying at which point I went wrong would be greatly appreciated. The main function is incomplete, and I think I shouldn't have much trouble with that part.

  // Shortest route.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
void shortest_Distance(int adj[][100], int distance[], int shortest[], int IN[], int n, int nodestart)
{
	//adj is the adjacency matrix, IN is include
	//1. Initialize Arrays distance,shortest,and IN
	for (int j = 0; j < n; j++)
	{
		distance[j] = adj[nodestart][j];
	}
	for (int j = 0; j < n; j++)
	{
		shortest[j] = nodestart;
	}
	for (int j = 0; j < n; j++)
	{
		IN[j] = 0; //null
	}
	IN[0] = nodestart;
	
	int min = distance[0];
	for (int i = 1; i < n; i++)
	{
		//2. Find the min in the array distance
		if (distance[i] < min)
			min = distance[i];
		//3.add the node to IN
		IN[i] = IN[0]+min;
		//4. Find the min of two distances.

	}
	

}

int _tmain(int argc, _TCHAR* argv[])
{
	char name[100] = { "x,1,2,3,4" };
	int adj[100][100] =
	{
		{ 0, 3, 8, 4, 0, 10 },
		{ 3, 0, 0, 6, 0, 0 },
		{ 8, 0, 0, 0, 7, 0 },
		{ 4, 6, 0, 0, 1, 3 },
		{0, 0, 7, 1, 0, 1 },
		{ 10, 0, 0, 3, 1, 0 }

	};
	//shortest_Distance(adj,);
	return 0;
}

[Gaminic]

I'm not sure what you are trying to do in your algorithm. Nowhere in your function do you pass a destination point, so I'll assume you're trying to compute the shortest path from nodestart to every other node.

"shortest" sounds like it should save the path so far, or the shortest distance path to this node so far, but it saves a single node per node, or one path? It is never used again, so I don't have more info to go on.

"IN" should probably be a list of nodes already checked (single-pass algorithm, such as (Dijkstra's). IN is initialised as 0, so I assumed you would be tagging nodes that are checked (eg. IN[3] == 1 signifies node 3 is already evaluated).
Later, IN[0] is initialised as [i]nodestart, so now I'm assuming you're building a sequential list (eg. IN[3] contains the 4th visited node). However, then you assign it a value of IN[0] + distance. What are you trying to store?


Your loop finds the lowest value in distance[], but distance only stores the distances to the starting node. How will it move ahead? It doesn't check whether a node is in. It finds the lowest distance but doesn't actually remember the node it relates to.


Can you explain how your algorithm is supposed to work, in words? I'm having trouble distilling an algorithm from your code. If you are looking at a Dijkstra's, you should follow the pseudocode from Wikipedia or some other source.